Capítulo 11

Aplicações do transporte de massa

11.1 Percolação invariante

A percolação invariante estende os modelos de elos e de sítios, preservando as simetrias do grafo, mas permitindo dependências entre os estados das arestas ou dos vértices.

A exigência é que a distribuição da configuração permaneça a mesma quando aplicamos um automorfismo do grafo. A percolação de Bernoulli (ou i.i.d.) é um caso particular: cada aresta ou vértice é declarado aberto com probabilidade $p$, independentemente dos demais. A invariância, porém, não exige independência; ela admite tanto dependências locais quanto correlações de longo alcance.

Definição 11.1 (Percolação invariante)

Seja $G$ um grafo. Seja $\mathbb {P}$ uma medida de probabilidade em algum dos conjuntos $2^{V(G)}, 2^{E(G)}$ ou $2^{V(G)\cup E(G)}$. Seja $\Omega $ o subconjunto aleatório associado (isto é, a configuração aleatória correspondente). Dizemos que $\mathbb {P}$ (ou $\Omega $) é uma percolação invariante se $\mathbb {P}$ é invariante sob a ação de $\operatorname {Aut}(G)$; ou seja, se para todo $\varphi \in \operatorname {Aut}(G)$, a medida de probabilidade $\mathbb {P}\circ \varphi ^{-1}$ coincide com $\mathbb {P}$. Em outras palavras, $\varphi \, \Omega $ e $\Omega $ têm a mesma distribuição.

Quando desejamos distinguir entre os casos $2^{V(G)}$, $2^{E(G)}$ ou $2^{V(G)\cup E(G)}$ acima, diremos que $\mathbb {P}$ (ou $\Omega $) é uma percolação invariante de sítios (resp. elos, resp. mista).

Exercício Seja $G$ um grafo de Cayley. Mostre que tanto a percolação de sítios quanto a de elos em $G$ são percolações invariantes.

Exemplo 11.1

Pode $\Omega $ consistir, quase certamente, em um único vértice? Se $G$ é transitivo, não existe percolação invariante tal que $|\Omega |=1$ quase certamente.

De fato, se houvesse uma medida $\mathbb {P}$ tal, então $\mathbb {P}[\Omega = \{ x\} ]$ seria constante independentemente de $x$ (pela transitividade). Portanto,

\[ 1 \; =\; \sum _{x}\, \mathbb {P}[\Omega = \{ x\} ] \; =\; \sum _{x}\, p \; =\; \infty \]

Exemplo 11.2

Seja $G$ transitivo. Pode $\Omega $ ser, quase certamente, um conjunto finito e não vazio de vértices? Isto é, existe uma percolação invariante $\Omega $ tal que $0 \lt |\Omega | \lt \infty $ quase certamente?

Se houvesse tal medida $\mathbb {P}$, então definimos $\Omega '$ escolhendo-se inicialmente $\Omega $ segundo $\mathbb {P}$ e, em seguida, escolhendo-se uniformemente um vértice $x$ de $\Omega $, e fixando $\Omega ' = \{ x\} $. Isto é,

\[ \mathbb {P}\bigl[\Omega ' = \{ x\} \, \big|\, (\Omega )\bigr] \; =\; \frac{\mathbf{1}_{\{ x \in \Omega \} }}{|\Omega |}. \]

Afirmamos que $\Omega '$ é uma percolação invariante, o que contradiz o exemplo anterior.

De fato, seja $\varphi \in \operatorname {Aut}(G)$. Então,

\[ \mathbb {P}\bigl[\varphi \Omega ' = \{ x\} \, \big|\, (\Omega )\bigr] \; =\; \mathbb {P}\bigl[\Omega ' = \{ \varphi ^{-1}x\} \, \big|\, (\Omega )\bigr] \; =\; \frac{\mathbf{1}_{\{ \varphi ^{-1}x \in \Omega \} }}{|\Omega |} \; =\; \frac{\mathbf{1}_{\{ x \in \varphi \, \Omega \} }}{|\varphi \, \Omega |} \; =\; \mathbb {P}\bigl[\Omega ' = \{ x\} \, \big|\, (\varphi \, \Omega )\bigr]. \]

Como $\Omega $ e $\varphi \, \Omega $ têm a mesma distribuição, isso mostra que $\Omega '$ é invariante.

Exemplo 11.3

Se $G$ é transitivo, então o número de componentes finitas em uma percolação invariante $\Omega $ deve ser 0 ou $\infty $ quase certamente.

Com efeito, suponha que $N$ denote o número de componentes finitas, e que $\mathbb {P}[\, 0 \lt N \lt \infty \, ] \gt 0$. Então, definimos $\Omega '$ como a união de todas as componentes finitas; a medida $\mathbb {P}\bigl[\Omega ' \in \cdot \, \big|\, (0 \lt N \lt \infty )\bigr]$ é uma percolação invariante para a qual $\mathbb {P}[\, |\Omega '| \lt \infty \, \mid \, 0 \lt N \lt \infty ] = 1$.

Exemplo 11.4

Seja $\mathbb {P}$ uma percolação invariante e seja $\Psi $ o conjunto (aleatório) de todos pontos de “$r$-trifurcação”. Então, $\Psi $ também é uma percolação invariante. Portanto, $|\Psi | \in \{ 0, \infty \} $ quase certamente.

Proposição 11.1

Seja $\mathbb {P}$ uma percolação invariante em algum grafo de Cayley $G$. Para qualquer $x \in G$, a componente de $x$, denotada por $\mathcal{C}(x)$, contém ou 0 ou infinitos pontos de trifurcação.

Demonstração ▼

Para cada configuração $\omega \in \{ 0,1\} ^{V(G)}$ e $x,y \in G$, definimos

\[ F(x,y,\omega ) \; =\; \begin{cases} 0, & \text{se a componente de }x\text{ em }\omega \text{ contiver 0 ou infinitos pontos $r$-trifurcação;}\\ \tfrac {1}{N}, & \text{caso contrário,} \end{cases} \]

onde $N$ é o número de pontos $r$-trifurcação na componente de $x$. Mais precisamente, se a componente de $x$ contém exatamente $N$ pontos $r$-trifurcação, definimos

\[ F(x,y,\omega ) \; =\; \begin{cases} \tfrac {1}{N}, & \text{se }y\text{ é ponto de trifurcação;}\\ 0, & \text{caso contrário.} \end{cases} \]

Observamos que $F(\varphi x, \varphi y, \varphi \, \omega ) = F(x,y,\omega )$ para $\varphi \in \operatorname {Aut}(G)$. Assim, definindo $f(x,y) := \mathbb {E}[\, F(x,y,\Omega )\, ]$, temos que $f$ é uma função invariante. Pelo princípio de transporte de massa,

\[ \sum _{x} f(o,x) \; =\; \sum _{x} f(x,o). \]

Por definição, $\sum _{x} F(o,x,\omega )$ é igual a 0 ou 1. Portanto, $\sum _{x} f(o,x) \le 1$.

Denote por $A$ o evento de que $o$ é um ponto $r$-trifurcação e sua componente possui um número positivo e finito de pontos $r$-trifurcação. Para toda configuração $\omega \in A$, a componente de $o$ é infinita e, para qualquer $x$ nessa componente, $F(x,o,\omega )=\tfrac {1}{N}$. Logo $\sum _xF(x,o,\omega )=\infty $ em $A$. Se $\mathbb P(A)\gt 0$, teríamos

\[ 1 \; \ge \; \sum _{x} f(x,o) \; \ge \; \mathbb {E}\! \Bigl[\sum _{x}F(x,o,\omega )\, \mathbf{1}_{A}\Bigr] \; =\; \infty , \]

contradição. Assim, para cada vértice $o$,

\[ \mathbb P\bigl(o\text{ é trifurcação e sua componente contém apenas finitas trifurcações}\bigr)=0. \]

Como $V(G)$ é enumerável, a união desses eventos sobre todos os vértices também tem probabilidade zero. Se alguma componente possuísse um número positivo e finito de pontos de trifurcação, um desses pontos pertenceria justamente a essa união. Logo, quase certamente, cada componente contém ou nenhum ponto de trifurcação ou infinitos pontos de trifurcação.

11.2 Percolação crítica em grupos não amenáveis

Recordemos a definição de $\Phi (G)$, a constante de Cheeger do grafo $G$, e que $G$ é amenável se e somente se $\Phi (G) = 0$.

O teorema de Benjamini, Lyons, Peres e Schramm descreve a percolação no ponto crítico para a classe de grafos a seguir.

Teorema 11.2

Se $G$ é um grafo não amenável unimodular e transitivo, então $\theta (p_c) = 0$.

A prova será dividida em duas etapas: primeiro mostramos que o número de componentes infinitas em $p_c$ não pode ser 1; em seguida, que não pode ser $\infty $.

Trataremos da percolação por elos; o caso de sítios é análogo.

11.3 Exclusão de uma componente infinita única: $k_{p_c} \neq 1$

Lema 11.3

Seja $\Omega $ uma percolação invariante em um grafo unimodular e transitivo $G$ de modo que todas as componentes de $\Omega $ sejam finitas. Então,

\[ \mathbb {E}\bigl[\operatorname {deg}_{\Omega }(x)\bigr] \; \le \; \operatorname {deg}_{G} - \Phi (G). \]

Consequentemente, se $\{ \Omega _{\varepsilon }\} _{\varepsilon }$ é uma família de configurações de percolação invariante tal que $\lim _{\varepsilon \to 0}\, \mathbb {P}[\Omega _{\varepsilon }(e)=1] = 1$ para toda aresta $e$, e se $G$ é não amenável, então existe $\varepsilon \gt 0$ para o qual $\Omega _{\varepsilon }$ possui uma componente infinita com probabilidade positiva. Se, além disso, a lei de $\Omega _\varepsilon $ é ergódica, essa probabilidade é um.

Demonstração ▼

Seja $S$ finito, conexo e não vazio. Como $G$ é transitivo, ele é regular; denotemos seu grau por $\deg _G$. Contando, para cada vértice de $S$, as arestas que permanecem dentro de $S$, obtemos

\[ \sum _{x\in S}\deg _S(x) =\deg _G|S|-|\partial _eS|. \]

Cada vértice de $\partial S$ é extremo exterior de pelo menos uma aresta de $\partial _eS$. Portanto

\[ |\partial _eS|\ge |\partial S|\ge \Phi (G)|S|, \]

e assim

\[ \frac1{|S|}\sum _{x\in S}\deg _S(x) \le \deg _G-\Phi (G). \]

Como todas as componentes de $\Omega $ são finitas, defina-se

\[ F(x,y,\Omega ) \; =\; \frac{\deg _\Omega (x)}{\lvert C(x)\rvert } \; \cdot \; 1_{\{ \, x\leftrightarrow y \text{ (em } \Omega )\} }. \]

Assim, definimos $f(x,y) := \mathbb {E}\bigl[F(x,y,\Omega )\bigr]$, que é uma função invariante. Pelo princípio de transporte de massa,

\[ \mathbb {E}\bigl[\deg _\Omega (x)\bigr] \; =\; \sum _y\, f(x,y) \; =\; \sum _y\, f(y,x) \; =\; \mathbb {E}\Bigl[ \tfrac {1}{\lvert C(x)\rvert } \sum _{y\leftrightarrow x}\deg _\Omega (y)\Bigr] \; \le \; \deg _G \; -\; \Phi (G), \]

pois cada $C(x)$ é finita e conexa.

Se $G$ não for amenável, então $\Phi (G)\gt 0$. Fixe um vértice $x$. Como ele possui apenas finitos vizinhos e, para cada aresta $e$ incidente a $x$, temos $\mathbb P[\Omega _\varepsilon (e)=1]\to 1$, podemos escolher $\varepsilon $ tão pequeno que

\[ \mathbb P[\Omega _\varepsilon (x\sim y)=1] \gt 1-\deg _G^{-1}\Phi (G) \]

para todo vizinho $y$ de $x$. Segue que

\[ \mathbb {E}\bigl[\deg _{\Omega _\varepsilon }(x)\bigr] \; =\; \sum _{y \sim x}\, \mathbb {P}\bigl[\Omega _\varepsilon (x\sim y)=1\bigr] \; \gt \; \deg _G \; -\; \Phi (G). \]

Se todas as componentes de $\Omega _\varepsilon $ fossem finitas quase certamente, a primeira parte daria a desigualdade oposta. Logo $\Omega _\varepsilon $ possui uma componente infinita com probabilidade positiva; sob ergodicidade, o evento de existência de uma componente infinita é invariante e, portanto, tem probabilidade um.

Teorema 11.4

Seja $G$ um grafo não amenável unimodular e transitivo. Seja $k_{p_c}$ o número de componentes infinitas na percolação de elos em $G$ com parâmetro $p_c$. Então $\mathbb {P}[\, k_{p_c}=1\, ] = 0$.

Demonstração ▼

Considere o acoplamento natural das configurações de percolação $ (\Omega _p)_{p \in [0,1]} $. Suponha, por contradição, que em $p_c$ exista quase certamente uma única componente infinita, que denotaremos por $\mathcal C_\infty $. A hipótese é invariante e, pela ergodicidade da percolação de Bernoulli, essa é precisamente a situação correspondente a $k_{p_c}=1$.

Para cada vértice $x\in V(G)$, defina

\[ c(x)=\left\{ z\in \mathcal C_\infty : d_G(x,z)=d_G(x,\mathcal C_\infty )\right\} . \]

O conjunto $c(x)$ é não vazio. Além disso, está contido numa esfera finita em torno de $x$; pela local finitude de $G$, é finito. A construção é equivariante: aplicar um automorfismo à configuração leva $c(x)$ em $c(\varphi x)$.

Para $0\lt \varepsilon \lt p_c$, definimos a configuração $H_\varepsilon $ declarando aberta uma aresta $e=\{ x,y\} $ se, e somente se,

$d_G(x,\mathcal C_\infty )\lt \varepsilon ^{-1}$ e $d_G(y,\mathcal C_\infty )\lt \varepsilon ^{-1}$;
todos os vértices de $c(x)\cup c(y)$ pertencem a uma mesma componente de $\Omega _{p_c-\varepsilon }$.

Como o acoplamento natural e a regra $x\mapsto c(x)$ são equivariantes, $H_\varepsilon $ é uma percolação invariante.

Usaremos as seguintes propriedades de $H_\varepsilon $.

1. Monotonicidade. Se $\varepsilon \gt \delta \gt 0$, então $p_c-\varepsilon \lt p_c-\delta $ e a condição de distância para $H_\varepsilon $ é mais restritiva. Logo

\[ H_\varepsilon \le H_\delta . \]

2. Cada aresta aparece quando $\varepsilon \downarrow 0$. Fixe $e=\{ x,y\} $. O conjunto $c(x)\cup c(y)$ é finito e está contido na componente conexa $\mathcal C_\infty $ de $\Omega _{p_c}$. Podemos, portanto, escolher uma coleção finita de caminhos abertos em $\Omega _{p_c}$ que conecta todos esses vértices. No acoplamento natural, uma aresta $f$ pertence a $\Omega _{p_c}$ quando $U(f)\le p_c$; como os rótulos têm distribuição contínua, quase certamente nenhum dos rótulos da coleção finita é exatamente $p_c$. Assim, existe $\eta (e)\gt 0$ tal que todos esses caminhos já estão abertos em $\Omega _{p_c-\varepsilon }$ sempre que $0\lt \varepsilon \lt \eta (e)$. Reduzindo ainda mais $\varepsilon $, a condição de distância também é satisfeita. Portanto

\[ H_\varepsilon (e)\uparrow 1 \qquad \text{quase certamente quando }\varepsilon \downarrow 0, \]

e, por convergência dominada,

\[ \mathbb P[H_\varepsilon (e)=1]\longrightarrow 1. \]

Pelo Lema 11.3, para algum $\varepsilon \gt 0$ suficientemente pequeno, $H_\varepsilon $ possui uma componente infinita com probabilidade positiva. Fixe, numa configuração desse evento, um caminho simples infinito

\[ x_0,x_1,x_2,\ldots \]

formado por arestas de $H_\varepsilon $.

3. Um caminho infinito em $H_\varepsilon $ produz uma componente infinita abaixo de $p_c$. Ponha

\[ U=\bigcup _{j\ge 0}c(x_j). \]

Esse conjunto é infinito. De fato, se $U$ fosse finito, cada $x_j$ estaria a distância menor que $\varepsilon ^{-1}$ de algum vértice de $U$; todos os $x_j$ pertenceriam então à união finita de bolas de raio $\lceil \varepsilon ^{-1}\rceil $ centradas nos vértices de $U$. Essa união é finita pela local finitude, em contradição com o fato de o caminho $(x_j)$ ser simples e infinito.

Por outro lado, se $x_j\sim x_{j+1}$ é uma aresta de $H_\varepsilon $, a definição garante que $c(x_j)\cup c(x_{j+1})$ está contido em uma única componente de $\Omega _{p_c-\varepsilon }$. Encadeando essa afirmação ao longo do caminho, todo o conjunto $U$ pertence a uma mesma componente de $\Omega _{p_c-\varepsilon }$. Como $U$ é infinito, essa componente é infinita.

Obtivemos, com probabilidade positiva, uma componente infinita para o parâmetro $p_c-\varepsilon \lt p_c$, contradizendo a definição de $p_c$. Logo

\[ \mathbb P(k_{p_c}=1)=0. \]

Figura 11.1 Exemplo esquemático da configuração H_ε : em azul a componente Omega ; em vermelho, conexões adicionais em H_ε . — Figura 11.1 Exemplo esquemático da configuração $ H_\varepsilon $: em azul a componente $ \Omega $; em vermelho, conexões adicionais em $ H_\varepsilon $.

11.4 Exclusão de infinitas componentes infinitas: $k_{p_c}\neq \infty $

Recordemos a definição de um ponto $r$-trifurcação $x$; esse evento é denotado por $\Psi _{r}(x)$. Temos $\Psi _{r}(x) = \{ M_{r} \ge 3 \} $ onde $M_{r} = (N_{r})_{0,\, E(B(x,r))}$ e $N_{r}$ é o número de componentes infinitas que intersectam a bola de raio $r$; ou seja, $\Psi _{r}(x)$ é o evento de que, ao tornar todas as arestas em $B(x,r)$ a estarem fechadas, existam ao menos 3 caminhos infinitos a partir de $\partial B(x,r)$. Tal evento é independente de $\mathcal{F}_{\, E(B(x,r))}$.

Lema 11.5

Seja $\Omega $ uma percolação invariante em um grafo unimodular e transitivo $G$. Então, se

\[ \mathbb {P}\Bigl[\Psi _{1}(x),\, |\mathcal{C}_{\Omega }(x)|=\infty \Bigr] \; \gt \; 0, \]

segue que

\[ \mathbb {E}\Bigl[\operatorname {deg}_{\Omega }(x)\, \Bigm |\, (|\mathcal{C}_{\Omega }(x)|=\infty )\Bigr] \; \gt \; 2. \]

Demonstração ▼

Defina $R(x,y,\Omega )$ como o indicador do evento de que exista um caminho simples infinito da forma $(\, x=x_0,\, y=x_1,\, x_2,\, x_3,\ldots )$ com $\Omega (x_n \sim x_{n+1})=1$ para todo $n$. Defina

\[ F(x,y,\Omega ) \; =\; \begin{cases} 2\, R(x,y,\Omega ), & \text{se } R(y,x,\Omega )=0,\\ \, R(x,y,\Omega ), & \text{caso contrário}. \end{cases} \]

Ou seja, $F(x,y,\Omega )=1$ se é possível ir ao infinito a partir de $x$ em duas direções, com uma delas passando por $y$; se é possível ir ao infinito via $y$ porém só existe uma direção, então $F(x,y,\Omega )=2$. A regra atribui pesos distintos às duas possibilidades de prolongamento de um caminho até o infinito.

A função $F$ é invariante e, consequentemente, $f(x,y)\coloneqq \mathbb {E}[F(x,y,\Omega )]$ é invariante.

Note que

\[ F(x,y,\Omega ) + F(y,x,\Omega ) \; =\; 2\, \mathbf{1}_{\{ \Omega (x \sim y)=1\} }\; \mathbf{1}_{\{ |\mathcal{C}_{\Omega }(x)|=\infty \} }. \]

Logo,

\[ \sum _{y} \Bigl[F(x,y,\Omega )\, +\, F(y,x,\Omega )\Bigr] \; =\; 2\, \operatorname {deg}_{\Omega }(x)\, \mathbf{1}_{\{ |\mathcal{C}_{\Omega }(x)|=\infty \} }. \]

O Princípio de Transporte de Massa implica

\[ \mathbb {E}\! \bigl[\operatorname {deg}_{\Omega }(x)\, \mathbf{1}_{\{ |\mathcal{C}_{\Omega }(x)|=\infty \} }\bigr] \; =\; \frac12\sum _{y}\bigl[f(x,y)+f(y,x)\bigr] \; =\; \sum _{y} f(x,y) \; =\; \mathbb {E}\! \Bigl[\sum _{y}F(x,y,\Omega )\Bigr]. \]

Sempre que $|\mathcal{C}_{\Omega }(x)|=\infty $ e $x$ é um ponto de trifurcação, obtemos $\sum _{y}F(x,y,\Omega )\ge 3$. Além disso, para qualquer $x$ com $|\mathcal{C}_{\Omega }(x)|=\infty $, deve existir ao menos um caminho de $x$ até o infinito, de modo que $\sum _{y}F(x,y,\Omega )\ge 2$. Portanto,

\[ \begin{aligned} \mathbb {E}\! \Bigl[\operatorname {deg}_{\Omega }(x)\, \mathbf{1}_{\{ |\mathcal{C}_{\Omega }(x)|=\infty \} }\Bigr] & =\sum _{y}\mathbb {E}\Bigl[F(x,y,\Omega )\, \mathbf{1}_{\{ \Psi _{1}(x),\, |\mathcal{C}_{\Omega }(x)|=\infty \} }\Bigr] \\ & \quad +\, \mathbb {E}\Bigl[F(x,y,\Omega )\, \mathbf{1}_{\{ \Psi _{1}(x)^c,\, |\mathcal{C}_{\Omega }(x)|=\infty \} }\Bigr]\\ & \ge 3\, \mathbb {P}\bigl[\Psi _{1}(x),\, |\mathcal{C}_{\Omega }(x)|=\infty \bigr] \\ & \quad +\, 2\, \mathbb {P}\bigl[\Psi _{1}(x)^c,\, |\mathcal{C}_{\Omega }(x)|=\infty \bigr]\\ & =\; 2\, \mathbb {P}\bigl[|\mathcal{C}_{\Omega }(x)|=\infty \bigr]\; +\; \mathbb {P}\bigl[\Psi _{1}(x),|\mathcal{C}_{\Omega }(x)|=\infty \bigr]\\ & \gt \; 2\, \mathbb {P}\bigl[|\mathcal{C}_{\Omega }(x)|=\infty \bigr]. \end{aligned} \]

Portanto,

\[ \mathbb {E}\! \Bigl[\operatorname {deg}_{\Omega }(x)\, \Bigm |\, (|\mathcal{C}_{\Omega }(x)|=\infty )\Bigr] \; \gt \; 2. \]

Além disso,

\[ \mathbb {E}[\deg _\Omega (x) \mid |C_\Omega (x)| = \infty ] = \frac{\mathbb {E}[\deg _\Omega (x) \cdot \mathbf{1}_{\{ |C_\Omega (x)| = \infty \} }]}{\mathbb {P}[|C_\Omega (x)| = \infty ]}. \]

Substituindo:

\[ \frac{\mathbb {E}[\deg _\Omega (x) \cdot \mathbf{1}_{\{ |C_\Omega (x)| = \infty \} }]}{\mathbb {P}[|C_\Omega (x)| = \infty ]} \gt 2, \]

portanto,

\[ \mathbb {E}[\deg _\Omega (x) \mid |C_\Omega (x)| = \infty ] \gt 2. \]

Medida produto condicional: percolação invariante e Bernoulli

Seja $ G = (V,E) $ um grafo localmente finito. Considere:

Uma medida de percolação invariante $ \mu $ sobre $ \{ 0,1\} ^E $, ou seja, $ \omega \in \{ 0,1\} ^E $ é uma configuração aleatória onde cada aresta está aberta ($ \omega (e)=1 $) ou fechada ($ \omega (e)=0 $);
Para cada configuração $ \omega \sim \mu $, as componentes abertas (componentes conexas do subgrafo induzido por $ \omega $) são denotadas por $ \{ \mathcal{C}_i(\omega )\} _{i \in I} $, onde $ I $ é um conjunto (aleatório) de índices.

Sobre essa configuração, definimos uma segunda percolação de Bernoulli com parâmetro $ p \in [0,1] $, restrita às arestas abertas de $ \omega $.

Definição 11.2 (Percolação invariante e Bernoulli)

Seja $ \nu $ a medida de probabilidade associada a uma percolação invariante.

Para cada realização $ \omega $ da percolação invariante, definimos uma configuração de percolação invariante + Bernoulli, $ \omega ^{\prime } \in \{ 0,1\} ^E $ por:

Arestas $ e \in \omega $: abertas com probabilidade $ p \in [0,1] $, independentemente entre si;
Arestas $ e \notin \omega $: fixadas como fechadas, ou seja, $ \omega ^{\prime }(e) = 0 $ com probabilidade 1.

A medida de percolação invariante + Bernoulli resultante é a medida produto condicional $ \mathbb {P}_{\nu }^p $ sobre $ \omega ^{\prime } \in \{ 0,1\} ^E $ dada por:

\[ \mathbb {P}_{\nu }^p(\omega ^{\prime }) = \int \mathbb {P}_p(\omega ^{\prime } \mid \omega ) \, d\nu (\omega ), \]

onde $ \mathbb {P}_p(\cdot \mid \omega ) $ é a medida produto de Bernoulli com parâmetro $p$, condicionada à configuração $ \omega $, ou seja,

\[ \mathbb {P}_p(\omega ^{\prime } \mid \omega ) = \prod _{e \in \omega } p^{\omega ^{\prime }(e)} (1 - p)^{1 - \omega ^{\prime }(e)} \cdot \prod _{e \notin \omega } \delta _0(\omega ^{\prime }(e)). \]

onde

\[ \delta _0(\omega ^{\prime }(e)) = \begin{cases} 1, & \text{se } \eta (e) = 0; \\ 0, & \text{caso contrário}. \end{cases} \]

Lema 11.6

Seja $\Omega $ uma percolação invariante em um grafo unimodular e transitivo $G$. Suponha que todas as componentes de $\Omega $ sejam árvores (possivelmente finitas) quase certamente. Então, se

\[ \mathbb {P}\bigl[\Psi _{1}(x),\; x\leftrightarrow \infty \bigr]\gt 0, \]

segue que, quase certamente, existe alguma componente $\mathcal{C}$ de $\Omega $ tal que a percolação de elos de Bernoulli em $\mathcal{C}$ satisfaça $p_{c}\lt 1$.

Demonstração ▼

Vimos que se $\mathbb {P}[\Psi _{1}(x),\, x\leftrightarrow \infty ]\gt 0$, então

\[ m := \mathbb {E}\bigl[\operatorname {deg}_{\Omega }(x)\, \bigm |\, (x\leftrightarrow \infty )\bigr] \; \gt \; 2. \]

Escolhemos $p\lt 1$ suficientemente próximo de $1$ para que $m\, p\gt 2$. Essa escolha usa a desigualdade estrita $m\gt 2$, e não apenas $m\ge 2$.

Seja $\Omega '$ a percolação de elos de Bernoulli de parâmetro $p$ sobre $\Omega $. Então

\[ \begin{aligned} \mathbb {E}\bigl[\operatorname {deg}_{\Omega '}(x)\, \bigm |\, (|\mathcal{C}_{\Omega }(x)|=\infty )\bigr] & =\; \sum _{y\sim x}\mathbb {P}\bigl[\Omega (x\sim y)=1\, \big|\, (|\mathcal{C}_{\Omega }(x)|=\infty )\bigr]\, p\\ & =\; \mathbb {E}\bigl[\operatorname {deg}_{\Omega }(x)\, \bigm |\, (|\mathcal{C}_{\Omega }(x)|=\infty )\bigr]\; p \; =\; m\, p\; \gt \; 2. \end{aligned} \]

Nessa construção, cada aresta de $ \Omega $ tem probabilidade $ p $ de permanecer em $ \Omega ' $.

Para comparar esse grau médio com o de uma componente finita, usamos a identidade $|E(T)|=|T|-1$ para uma árvore finita $T$. Portanto,

\[ 2\, |T| \; \gt \; 2\, |E(T)| \; =\; \sum _{x,y\in T}\mathbf{1}_{\{ x\sim y\} } \; =\; \sum _{x\in T}\operatorname {deg}_{\, T}(x). \]

Se todas as componentes de $\Omega '$ são árvores finitas quase certamente, consideramos a função de transporte $ F(x, y, \Omega ) $ definida por

\[ F(x, y, \Omega ) := \frac{\deg _{\Omega '}(x)}{|C_{\Omega '}(x)|} \cdot \mathbf{1}_{\{ y \in C_{\Omega '}(x)\} } \cdot \mathbf{1}_{\{ |C_\Omega (x)| = \infty \} }, \]

que representa a quantidade de massa que o vértice $ x $ envia a $ y $, normalizada pelo tamanho de sua componente em $ \Omega ' $, e condicionada ao fato de $ x $ pertencer a uma componente infinita de $ \Omega $.

O Princípio de Transporte de Massa iguala a massa total esperada enviada à massa total esperada recebida:

\[ \mathbb {E}[\deg _{\Omega '}(x) \cdot \mathbf{1}_{\{ |C_\Omega (x)| = \infty \} }] = \mathbb {E} \left[ \sum _{y} F(y, x, \Omega ) \right]. \]

A massa recebida em $x$ pode ser escrita como

\[ \sum _y F(y, x, \Omega ) = \sum _{y \in C_{\Omega '}(x)} \frac{\deg _{\Omega '}(y)}{|C_{\Omega '}(x)|} \cdot \mathbf{1}_{\{ |C_\Omega (x)| = \infty \} } = \frac{1}{|C_{\Omega '}(x)|} \sum _{y \in C_{\Omega '}(x)} \deg _{\Omega '}(y) \cdot \mathbf{1}_{\{ |C_\Omega (x)| = \infty \} }. \]

Portanto,

\[ \mathbb {E}[\deg _{\Omega '}(x) \cdot \mathbf{1}_{\{ |C_\Omega (x)| = \infty \} }] = \mathbb {E}\left[ \frac{1}{|C_{\Omega '}(x)|} \sum _{y \in C_{\Omega '}(x)} \deg _{\Omega '}(y) \cdot \mathbf{1}_{\{ |C_\Omega (x)| = \infty \} } \right]. \]

Como, por hipótese, todas as componentes de $ \Omega ' $ são árvores finitas, para cada componente $ C $ temos

\[ \frac{1}{|C|} \sum _{y \in C} \deg _{\Omega '}(y) \lt 2, \]

e, portanto,

\[ \mathbb {E}[\deg _{\Omega '}(x) \cdot \mathbf{1}_{\{ |C_\Omega (x)| = \infty \} }] \lt 2 \cdot \mathbb {P}[|C_\Omega (x)| = \infty ]. \]

Por outro lado, o cálculo do grau médio forneceu

\[ \mathbb {E}[\deg _{\Omega '}(x) \cdot \mathbf{1}_{\{ |C_\Omega (x)| = \infty \} }] = mp \cdot \mathbb {P}[|C_\Omega (x)| = \infty ], \]

e, pela escolha de $ p $, temos $ mp \gt 2 $. Portanto,

\[ mp \cdot \mathbb {P}[|C_\Omega (x)| = \infty ] \gt 2 \cdot \mathbb {P}[|C_\Omega (x)| = \infty ], \]

o que leva a uma contradição.

Logo a hipótese de que todas as componentes de $ \Omega ' $ são finitas não pode ser verdadeira. Assim, $ \Omega ' $ contém quase certamente uma componente infinita, o que mostra que $ p_c \lt 1 $ para alguma componente $ \mathcal{C} \subseteq \Omega $.

Definimos a floresta geradora mínima livre $ \mathcal{F} $ de $ \Omega $ como o subconjunto de arestas $ e \in \Omega $ que não pertencem a nenhum ciclo de $ \Omega $ no qual $ e $ recebe o maior valor atribuído entre as arestas do ciclo.

Definição 11.3

Seja $(\Omega _p)_p$ o acoplamento natural de percolação de elos construído a partir das variáveis aleatórias independentes e identicamente distribuídas $U(e)_e$. Para cada $p$, definimos a floresta geradora mínima livre (FGM) $\mathcal{F}=\mathcal{F}_p$ do seguinte modo:

\begin{align*} \mathcal{F}(x\sim y)=& 1 \Longleftrightarrow \Omega _p(x\sim y)=1 \text{ e } \forall \text{ caminho finito }\gamma : x\to y,\gamma \subset \Omega _p, \\ \exists \, j, \, 0 & \le j\le |\gamma |-1:U(\gamma _j\sim \gamma _{j+1})\ge U(x\sim y). \end{align*}

A floresta geradora mínima livre de um grafo $ G $ com pesos aleatórios contínuos $ U(e) \in [0,1] $ atribuídos às arestas pode ser construída removendo-se de cada ciclo simples a aresta com o maior rótulo. Isso produz, com probabilidade 1, uma floresta livre de ciclos.

Exercício 11.1

Mostre que FGM é uma percolação invariante.

Lema 11.7

Seja $G$ um grafo transitivo e $\mathcal{F}= \mathcal{F}_{p_c}$ para $p_c = p_c(G)$. Então, quase certamente, para todo $x$, a componente $\mathcal{C}_{\mathcal{F}}(x)$ de $x$ em $\mathcal{F}$ é uma árvore que abrange $\mathcal{C}_{p_c}(x)$.

Em particular, se $x$ é um ponto de trifurcação em uma componente infinita de $\Omega _{p_c}$, então ele também é um ponto de trifurcação em uma árvore infinita em $\mathcal{F}_{p_c}$.

Demonstração ▼

É suficiente provar que para qualquer $x \sim y \in \Omega _{p_c}$, temos $y \leftrightarrow x$ em FGM.

Fixe $x \sim y \in \Omega _{p_c}$. Seja $u = U(x\sim y)$. Mostraremos que, se $x \nleftrightarrow y$ em FGM, então a componente $\mathcal{C}_u(x)$ em $\Omega _u$ é infinita.

Assuma que $y \nleftrightarrow x$ em FGM. Como $x \sim y \notin \mathcal{F}$, deve existir um caminho simples $\alpha : x\to y$ contido em $\mathcal{C}_u(x)$, ou seja, com $\alpha $ aberto em $\Omega _u$.

Se $\alpha $ for aberto em FGM, então $x \leftrightarrow y$ em FGM, contradizendo nossa suposição. Portanto, deve existir uma aresta $\alpha _\ell \sim \alpha _{\ell +1}$ que não pertence à FGM. No entanto, pela definição, isso proporciona um caminho simples $\gamma : \alpha _{\ell }\to \alpha _{\ell +1}$ tal que

\[ \max _{0\le j \le |\gamma |-1}\, U\bigl(\gamma _j\sim \gamma _{j+1}\bigr) \; \lt \; U\bigl(\alpha _\ell \sim \alpha _{\ell +1}\bigr)\; \le \; u \]

(já que $\alpha $ é aberta em $\Omega _u$). Logo, $E\bigl(\alpha \cup \gamma \bigr)\, \setminus \{ \alpha _\ell \sim \alpha _{\ell +1}\} $ é aberto em $\Omega _u$, e, portanto, contém um caminho simples $\beta :x\to y$ que também é aberto em $\Omega _u$.

Numa floresta há um único caminho simples entre quaisquer dois vértices da mesma componente conexa. Se a interseção $\gamma \cap \alpha $ contivesse um vértice $\alpha _j$ diferente dos extremos, haveria dois caminhos distintos em $F_{\lt w}$ ligando $\alpha _i$ a $\alpha _j$: um subcaminho de $\alpha $ e um de $\gamma $, formando um ciclo — impossível em $F_{\lt w}$. Logo $\gamma \cap \alpha =\{ \alpha _i,\alpha _{i+1}\} $.

Como $\alpha $ é simples, a concatenação indicada não repete vértices, portanto $\beta $ é simples.

De fato,

\[ \beta \; =\; (x_0,\, \ldots ,\, \alpha _\ell =\gamma _0,\, \ldots ,\, \gamma _{|\gamma |}=\alpha _{\ell +1},\, \ldots ,\, \alpha _{|\alpha |}), \]

o que implica $|\beta |=|\alpha |+|\gamma |-1\gt |\alpha |$.

Por indução, isso implica que, para qualquer $k$, há um caminho $\alpha :x\to y$ tal que $\alpha $ está aberto em $\Omega _u$ e $|\alpha |\gt k$. Logo, $|\, E(\mathcal{C}_u(x))\, |\gt k$ para todo $k$, o que significa $\bigl|\mathcal{C}_u(x)\bigr|=\infty $.

Mas como $ \mathcal{F}\subseteq \Omega _p $, na verdade temos:

\[ C_{\mathcal{F}}(x) \subseteq C_{\Omega _p}(x), \]

temos uma contradição.

Concluímos que, se $x\sim y \in \Omega _{p_c}$ e $x \nleftrightarrow y$ em FGM, então $|\mathcal{C}_u(x)|=\infty $, para $u = U(x\sim y)$. Como $U(x\sim y)\neq p_c$ quase certamente, temos

\[ \mathbb {P}\bigl[x\sim y \in \Omega _{p_c}\; \; \text{e}\; \; x \nleftrightarrow y\; \text{em FGM}\bigr] \; \le \; \mathbb {P}\bigl[\exists \, u \lt p_c,\; |\mathcal{C}_u(x)|=\infty \bigr] \; =\; 0. \]

Logo, mostramos que quase certamente, para qualquer $x\sim y \in \Omega _{p_c}$, também $x\leftrightarrow y$ em FGM. Isso implica, por um exercício abaixo, que $\mathcal{C}_{\mathcal{F}}(x)$ seja uma árvore que abrange $\mathcal{C}_{p_c}(x)$, para qualquer $x$, quase certamente.

Finalmente, se $x$ é um ponto de trifurcação em $\Omega _{p_c}$, então $|\mathcal{C}_{p_c}(x)|=\infty $, e remover as arestas adjacentes a $x$ dividiria $\mathcal{C}_{p_c}(x)$ em pelo menos 3 componentes infinitas. Se $T(x)$ for a árvore que abrange $\mathcal{C}_{p_c}(x)$ em FGM, então remover as arestas adjacentes a $x$ também dividirá $T(x)$ em 3 componentes infinitas.

Exercício 11.2

Mostre que, se para qualquer $x \sim y \in \Omega _{p}$ temos $x \leftrightarrow y$ em $\mathcal{F}_{p}$, então para cada componente conexa $\mathcal{C}_{p}(x)$ em $\Omega _{p}$, a componente $\mathcal{C}_{\mathcal{F}_{p}}(x)$ de $x$ em $\mathcal{F}_{p}$ é uma árvore que abrange $\mathcal{C}_{p}(x)$.

Exercício 11.3

Mostre que

\[ \mathbb {P}\Bigl[\exists \, u \lt p_{c}:\, \bigl|\mathcal{C}_{u}(x)\bigr|=\infty \Bigr] \; =\; 0. \]

Teorema 11.8

Seja $G$ um grafo não amenável, unimodular e transitivo. Seja $k_{p_{c}}$ o número de componentes infinitas na percolação de elos em $G$ com parâmetro $p_{c}$. Então,

\[ \mathbb {P}\bigl[k_{p_{c}} = \infty \bigr] \; =\; 0. \]

Demonstração ▼

Suponha, por contradição, que $ \mathbb {P}[k_{p_c} = \infty ] \gt 0 $.

Fixe $ r \gt 0 $. Defina o evento:

\begin{align*} \Psi _r(x) & := \left\{ \text{existem pelo menos três componentes infinitas de } \Omega _{p_c} \text{ conectadas a } \partial B(x,r) \right.\\ & \left. \text{ por caminhos abertos em } B(x,r) \right\} . \end{align*}

Como assumimos $ k_{p_c} = \infty $ temos que $p_{c} \lt 1$, então existe $ r $ tal que $ \mathbb {P}[\Psi _r(x)] \gt 0 $.

Então, se conectarmos quaisquer três componentes infinitas a partir de $\partial B(x,r)$ por caminhos abertos dentro de $B(x,r)$, obtemos

\[ \mathbb {P}\! \Bigl[\exists \, y \in B(x,r):\, \Psi _{1}(y),\, y\leftrightarrow \infty \; \Bigm |\; \Psi _{r}(x)\Bigr] \; \ge \; q\gt 0. \]

Pela transitividade, isso vale para qualquer vértice, e em particular

\[ \mathbb {P}\bigl[\Psi _{1}(x),\, x\leftrightarrow \infty \bigr]\gt 0. \]

Seja agora $\mathcal{F}= \mathcal{F}_{p_{c}}$ como no Lema 11.7. Aplicando o Lema 11.7, temos que, com probabilidade positiva, $ x $ é um ponto de trifurcação em uma árvore infinita da floresta geradora mínima livre $ \mathcal{F}_{p_c} \subseteq \Omega _{p_c} $.

Em seguida, pelo Lema 11.6, segue que $ \mathcal{F}_{p_c} $ contém quase certamente alguma subárvore $ \mathcal{C} \subseteq \Omega _{p_c} $ tal que

\[ p_c(\mathcal{C}) \lt 1. \]

No entanto, como $ \mathcal{C} \subseteq \mathcal{C}' $, onde $ \mathcal{C}' $ é uma componente de $ \Omega _{p_c} $, segue que:

\[ p_c(\mathcal{C}') \leq p_c(\mathcal{C}) \lt 1, \]

Entretanto,

\[ p_c(\mathcal{C'}) = 1. \]

Para ver isso suponha, por contradição, que

\[ p_c(\mathcal{C'}) \lt 1. \]

Então existe algum $ p \lt 1 $ tal que a percolação de Bernoulli com parâmetro $ p $ sobre $ \mathcal{C'} $ possui uma componente infinita com probabilidade positiva.

Contudo, como $ \mathcal{C'} \subseteq \Omega _{p_c} $, isso implica que $ \Omega _{p_c} $ percolaria com parâmetro $p \cdot p_c$ menor que $ p_c $, o que contradiz a definição do limiar crítico $ p_c $.

Portanto,

\[ \mathbb {P}[k_{p_c} = \infty ] = 0. \]

Lema 11.9 (Florestas na percolação)

Seja $ \Omega $ um processo de percolação $ \Gamma $-invariante em um grafo $ G $. Se, com probabilidade positiva, existe uma componente de $ \Omega $ com pelo menos três fins então (em um espaço de probabilidade ampliado) existe uma floresta aleatória $\mathcal{F} \subset \Omega $ tal que a distribuição do par $ (\mathcal{F}, \Omega ) $ é $ \Gamma $-invariante e, com probabilidade positiva, alguma componente de $\mathcal{F} $ possui ao menos três fins.

Demonstração ▼

Atribuímos variáveis aleatórias independentes com distribuição uniforme em $ [0,1] $ às arestas (independentemente da configuração $ \Omega $). Definimos a floresta geradora mínima livre $\mathcal{F} $ de $ \Omega $ como o subconjunto de arestas $ e \in \Omega $ que não pertencem a nenhum ciclo de $ \Omega $ no qual $ e $ recebe o maior valor atribuído entre as arestas do ciclo.

Não há ciclos em $\mathcal{F} $, pois, em qualquer ciclo de $\Omega $, a aresta de maior rótulo é removida. Além disso, toda componente de $\mathcal F$ contida em uma componente infinita de $\Omega $ é quase certamente infinita. Para ver isso, suponha que $K$ seja uma componente finita de $\mathcal F$ contida numa componente infinita de $\Omega $. Existe então ao menos uma aresta aberta de $\Omega $ com um extremo em $K$ e outro fora de $K$. Escolha, entre todas essas arestas, aquela de menor rótulo, digamos $e$.

A aresta $e$ não pode ser excluída da floresta. De fato, qualquer ciclo de $\Omega $ que contenha $e$ precisa sair de $K$ por $e$ e voltar a $K$ por outra aresta $f$ da mesma fronteira. Pela escolha de $e$ e pela continuidade dos rótulos, quase certamente $U(f)\gt U(e)$. Portanto $e$ não é a aresta de maior rótulo desse ciclo. Como isso vale para todo ciclo que contém $e$, a definição da floresta geradora mínima livre força $e\in \mathcal F$, contradizendo o fato de $K$ ser uma componente de $\mathcal F$. Logo, cada vértice de uma componente infinita de $ \Omega $ pertence a alguma árvore infinita de $\mathcal{F} $.

Suponha agora que a componente $ C_\Omega (x) $ tem, com probabilidade positiva, ao menos três fins. Fixe uma árvore finita $ T $ que contém $ x $ tal que, com probabilidade positiva, $ T \subset C_\Omega (x) $ e $ C_\Omega (x) \setminus V(T) $ possui ao menos três componentes infinitas. Com probabilidade positiva, ocorrem simultaneamente os seguintes eventos:

$ T \subset C_\Omega (x) $;
$ C_\Omega (x) \setminus V(T) $ possui ao menos três componentes infinitas;
todas as arestas de $ T $ recebem valores menores que $ \tfrac {1}{2} $;
todas as arestas incidentes a $ V(T) $, mas não pertencentes a $ T $, recebem valores maiores que $ \tfrac {1}{2} $.

Sob esse evento, $ T \subset \mathcal{F} $, e $ T $ pertence a uma árvore de $\mathcal{F} $ com ao menos três fins.

Aplicações do transporte de massa

11.1 Percolação invariante

11.2 Percolação crítica em grupos não amenáveis

11.3 Exclusão de uma componente infinita única: \(k_{p_c} \neq 1\)

11.4 Exclusão de infinitas componentes infinitas: \(k_{p_c}\neq \infty \)

Medida produto condicional: percolação invariante e Bernoulli