Capítulo 1

Grafos

Este capítulo reúne apenas a linguagem de teoria dos grafos usada ao longo do livro. O objetivo não é desenvolver a teoria em geral, mas fixar notação para distância, crescimento, simetrias e grafos de Cayley.

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 finito fechado sem repetições, exceto pelo vértice inicial/final.

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(r)=|B(o,r)|. \]

Em grafos transitivos, a ordem de crescimento não depende da escolha de \(o\).

Dizemos que \(G\) tem crescimento subexponencial se

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

e crescimento polinomial de grau 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.

Essas noções aparecem quando se converte decaimento de probabilidades de conexão em somabilidade espacial.

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\).

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 muda as distâncias em um grafo de Cayley, mas não muda sua geometria em grande escala. A linguagem adequada para essa afirmação é a de quase-isometria.

Definição 1.4
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\).