Capítulo 1

Grafos

Reunimos neste capítulo apenas a linguagem de teoria dos grafos que será usada adiante: distância, crescimento, simetrias e grafos de Cayley. A teoria aparece na medida em que é necessária para a percolação.

1.1 Grafos, caminhos e distância

Um grafo é um par \(G=(V,E)\), onde \(V=V(G)\) é o conjunto de vértices e \(E=E(G)\) é um conjunto de pares não ordenados de vértices. Se \(\{ x,y\} \in E\), escrevemos \(x\sim y\) e dizemos que \(x\) e \(y\) são adjacentes.

O grau de \(x\), denotado por \(\deg (x)\), é o número de seus vizinhos. Dizemos que \(G\) é localmente finito se todo vértice tem grau finito e \(d\)-regular se todo vértice tem grau \(d\). Salvo indicação em contrário, todos os grafos deste livro são infinitos, conexos e localmente finitos.

Exemplo 1.1 (A rede \(\mathbb Z^d\))
O grafo \(\mathbb Z^d\) tem conjunto de vértices \(\mathbb Z^d\) e uma aresta entre \(x\) e \(y\) quando
\[ \sum _{i=1}^d|x_i-y_i|=1. \]
Ele é infinito, conexo e \(2d\)-regular.

Definição 1.1
Um caminho é uma sequência \((x_0,x_1,\dots ,x_n)\) tal que \(x_i\sim x_{i+1}\) para todo \(i\). Seu comprimento é \(n\). Um caminho é simples ou autoevitante quando não repete vértices. Um ciclo é um caminho fechado \((x_0,\dots ,x_n)\) de comprimento \(n\ge 3\), com \(x_0=x_n\) e com \(x_0,\dots ,x_{n-1}\) dois a dois distintos.

A distância de grafo é

\[ d_G(x,y)=\inf \{ n:\text{existe um caminho de comprimento }n\text{ de }x\text{ a }y\} . \]

Como trabalharemos com grafos conexos, \(d_G(x,y)\lt \infty \) para quaisquer \(x,y\).

Para \(r\ge 0\), definimos a bola e a esfera

\[ B(x,r)=\{ y:d_G(x,y)\le r\} , \qquad S(x,r)=\{ y:d_G(x,y)=r\} . \]

Se \(A\subset V\), sua fronteira externa de vértices é

\[ \partial A=\{ y\notin A:\exists x\in A\text{ com }x\sim y\} , \]

e sua fronteira de arestas é

\[ \partial _eA=\{ \{ x,y\} \in E:x\in A,\ y\notin A\} . \]

Um subgrafo \(H\) de \(G\) possui \(V(H)\subset V(G)\) e \(E(H)\subset E(G)\). Se \(A\subset V(G)\), o subgrafo induzido por \(A\) contém todos os vértices de \(A\) e todas as arestas de \(G\) com os dois extremos em \(A\).

1.2 Árvores e crescimento

Um grafo sem ciclos é uma floresta; uma floresta conexa é uma árvore. Em uma árvore existe um único caminho simples entre dois vértices.

Quando distinguimos um vértice \(o\), chamado raiz, cada vértice \(x\ne o\) tem um único vizinho mais próximo de \(o\), seu pai; os vizinhos mais distantes de \(o\) são seus filhos. A árvore infinita \(d\)-regular será denotada por \(\mathbb T_d\).

O crescimento de um grafo é medido pelo volume das bolas. Fixado \(o\in V(G)\), escrevemos

\[ V_{G,o}(r)=|B(o,r)|. \]

A função \(V_{G,o}\) pode depender da raiz. As propriedades de crescimento consideradas abaixo, porém, não dependem dessa escolha. De fato, se \(d_G(o,o')=k\), então

\[ B(o,r)\subseteq B(o',r+k) \qquad \text{e}\qquad B(o',r)\subseteq B(o,r+k). \]

Em particular, em grafos transitivos as funções \(V_{G,o}\) são exatamente as mesmas para todas as raízes.

Dizemos que \(G\) tem crescimento subexponencial se

\[ \limsup _{r\to \infty }\frac{\log |B(o,r)|}{r}=0, \]

e crescimento polinomial de ordem no máximo \(D\) se existe \(C\lt \infty \) tal que

\[ |B(o,r)|\le C(1+r)^D \]

para todo \(r\). Em particular, \(\mathbb Z^d\) tem crescimento polinomial de ordem \(d\), enquanto \(\mathbb T_d\), para \(d\ge 3\), tem crescimento exponencial.

1.3 Grafos de Cayley

Seja \(\Gamma \) um grupo e seja \(S\subset \Gamma \) um conjunto finito de geradores. Podemos substituir \(S\) por \(S\cup S^{-1}\) e, portanto, supor \(S\) simétrico.

Definição 1.2
O grafo de Cayley \(\operatorname {Cay}(\Gamma ,S)\) tem conjunto de vértices \(\Gamma \) e uma aresta entre \(g\) e \(gs\) para cada \(g\in \Gamma \) e \(s\in S\).

A distância da identidade \(e\) a \(g\) coincide com o menor comprimento de uma palavra em \(S\) que representa \(g\); essa quantidade é a norma de palavra \(|g|_S\).

Exemplo 1.2

  • Para \(\Gamma =\mathbb Z^d\) e \(S=\{ \pm e_1,\dots ,\pm e_d\} \), obtemos a rede usual \(\mathbb Z^d\).

  • O grafo de Cayley do grupo livre em \(k\) geradores, usando os geradores e seus inversos, é a árvore regular de grau \(2k\).

  • A árvore regular de grau \(d\) também pode ser realizada como grafo de Cayley do produto livre de \(d\) cópias de \(\mathbb Z/2\mathbb Z\).

1.4 Automorfismos e grafos transitivos

Um automorfismo de \(G\) é uma bijeção \(\varphi :V(G)\to V(G)\) que preserva adjacências. O conjunto de todos os automorfismos forma o grupo \(\operatorname {Aut}(G)\).

Definição 1.3
O grafo \(G\) é transitivo se, para quaisquer \(x,y\in V(G)\), existe \(\varphi \in \operatorname {Aut}(G)\) tal que \(\varphi (x)=y\).

Definição 1.4
O grafo \(G\) é quase-transitivo se a ação de \(\operatorname {Aut}(G)\) sobre \(V(G)\) possui apenas um número finito de órbitas. Todo grafo transitivo é, em particular, quase-transitivo.

Em um grafo transitivo, todos os vértices têm o mesmo grau e qualquer quantidade definida apenas pela geometria enraizada do grafo é independente da raiz.

Proposição 1.1
Todo grafo de Cayley é transitivo.

Demonstração ▼

Se \(x,y,g\in \Gamma \), defina

\[ \varphi _{x,y}(g)=yx^{-1}g. \]

Essa aplicação é bijetiva e satisfaz \(\varphi _{x,y}(x)=y\). Se \(h=gs\) com \(s\in S\), então

\[ \varphi _{x,y}(h)=yx^{-1}gs=\varphi _{x,y}(g)s, \]

logo adjacências são preservadas. Portanto \(\varphi _{x,y}\) é um automorfismo do grafo de Cayley.

A recíproca é falsa: existem grafos transitivos que não são grafos de Cayley. Para os argumentos deste livro, a propriedade importante será a transitividade em si, e não uma representação específica por geradores.

1.5 Quase-isometrias

A escolha do conjunto finito de geradores altera as distâncias em um grafo de Cayley, mas preserva sua geometria em grande escala. Essa invariância é expressa pela noção de quase-isometria.

Definição 1.5
Sejam \((G,d_G)\) e \((H,d_H)\) grafos conexos. Uma aplicação \(f:G\to H\) é uma quase-isometria se existem constantes \(\lambda \ge 1\), \(C\ge 0\) e \(D\ge 0\) tais que
\[ \frac1\lambda d_G(x,y)-C \le d_H(f(x),f(y)) \le \lambda d_G(x,y)+C \]
para todos \(x,y\in G\), e todo vértice de \(H\) está a distância no máximo \(D\) da imagem de \(f\).

Teorema 1.2
Se \(\Gamma \) é um grupo finitamente gerado e \(S,T\) são dois conjuntos finitos de geradores, então \(\operatorname {Cay}(\Gamma ,S)\) e \(\operatorname {Cay}(\Gamma ,T)\) são quase-isométricos.

Demonstração ▼

Considere a identidade em \(\Gamma \). Como \(S\) é finito, existe

\[ L=\max _{s\in S}|s|_T\lt \infty . \]

Escreva

\[ g^{-1}h=s_1\cdots s_n, \qquad n=d_S(g,h), \qquad s_j\in S. \]

Pela desigualdade triangular para a norma de palavra,

\[ |g^{-1}h|_T \le \sum _{j=1}^n |s_j|_T \le nL =L\, d_S(g,h). \]

Como \(|g^{-1}h|_T=d_T(g,h)\), segue que

\[ d_T(g,h)\le Ld_S(g,h). \]

Trocando \(S\) e \(T\), existe \(L'\lt \infty \) tal que

\[ d_S(g,h)\le L'd_T(g,h). \]

Tomando

\[ \lambda =\max \{ L,L'\} , \]

obtemos

\[ \frac1\lambda d_S(g,h) \le d_T(g,h) \le \lambda d_S(g,h). \]

Logo a identidade é uma quase-isometria com \(C=0\) e, como é sobrejetiva, com \(D=0\).