Capítulo 10

Transporte de massa

O princípio de transporte de massa é uma ferramenta para explorar simetrias em grafos transitivos. A ideia é simples: cada vértice envia certa quantidade de massa aos demais, segundo uma regra compatível com as simetrias do grafo. Em situações unimodulares, a massa total esperada enviada por um vértice coincide com a massa total esperada recebida por ele.

Para formular esse princípio com precisão, começamos recordando algumas noções sobre ações de grupos.

10.1 Ações, órbitas e estabilizadores

Seja \(\Gamma \) um grupo que atua em um conjunto \(X\). Escrevemos

\[ \Gamma \times X\longrightarrow X, \qquad (g,x)\longmapsto g\cdot x, \]

com

\[ (gh)\cdot x=g\cdot (h\cdot x) \qquad \text{e}\qquad 1_\Gamma \cdot x=x. \]

Para \(x\in X\), definimos a órbita de \(x\) por

\[ \Gamma x=\{ g\cdot x:g\in \Gamma \} \]

e o estabilizador de \(x\) por

\[ \Gamma _x=\{ g\in \Gamma :g\cdot x=x\} . \]

A ação é chamada transitiva quando \(\Gamma x=X\) para todo \(x\in X\).

Se \(S\subset \Gamma \), usaremos ainda a notação

\[ Sx=\{ g\cdot x:g\in S\} . \]

A partir de agora, suponha que \(X\) seja um grafo localmente finito e que \(\Gamma \leq \operatorname {Aut}(X)\). Como os automorfismos preservam distâncias, para quaisquer \(x,y\in X\),

\[ \Gamma _x y\subseteq \{ z\in X:\operatorname {dist}(x,z)=\operatorname {dist}(x,y)\} . \]

Em particular, \(\Gamma _x y\) é finito.

Para \(x,y\in X\), defina também

\[ \Gamma _{x,y}=\{ g\in \Gamma :g\cdot x=y\} . \]

Esse conjunto pode ser vazio; quando não é, ele é simultaneamente uma classe lateral à esquerda de \(\Gamma _x\) e uma classe lateral à direita de \(\Gamma _y\).

Lema 10.1
Suponha que \(\Gamma \) atue em \(X\). Se \(\Gamma _{x,y}\neq \emptyset \) e \(g\in \Gamma _{x,y}\), então
\[ \Gamma _{x,y}=g\Gamma _x=\Gamma _y g. \]
Além disso, para todo \(z\in X\),
\[ |\Gamma _{x,y}z|=|\Gamma _x z|=|\Gamma _y(gz)|. \]

Demonstração ▼

Se \(h\in \Gamma _{x,y}\), então \(g^{-1}h\in \Gamma _x\), de modo que \(h\in g\Gamma _x\). Reciprocamente, se \(k\in \Gamma _x\), então \(gk\in \Gamma _{x,y}\). Logo,

\[ \Gamma _{x,y}=g\Gamma _x. \]

Analogamente, \(hg^{-1}\in \Gamma _y\) para todo \(h\in \Gamma _{x,y}\), e obtemos

\[ \Gamma _{x,y}=\Gamma _y g. \]

Da primeira identidade,

\[ \Gamma _{x,y}z=g(\Gamma _x z), \]

e a aplicação \(u\mapsto g u\) é uma bijeção entre \(\Gamma _x z\) e \(\Gamma _{x,y}z\). Portanto,

\[ |\Gamma _{x,y}z|=|\Gamma _x z|. \]

Como \(\Gamma _y=g\Gamma _xg^{-1}\), temos também

\[ \Gamma _y(gz)=g(\Gamma _xz), \]

o que prova a segunda igualdade.

Exercício 10.1
Mostre que
\[ |\Gamma _x y|=[\Gamma _x:\Gamma _x\cap \Gamma _y]. \]
Deduza que, se todos os estabilizadores \(\Gamma _x\) são finitos, então
\[ |\Gamma _x y|=|\Gamma _y x| \]
sempre que \(x\) e \(y\) pertencem à mesma órbita.

10.2 Funções invariantes

Uma função

\[ f:X\times X\longrightarrow [0,\infty ] \]

é chamada invariante sob a ação de \(\Gamma \) se

\[ f(gx,gy)=f(x,y) \]

para todos \(g\in \Gamma \) e \(x,y\in X\).

Interpretaremos \(f(x,y)\) como a quantidade de massa enviada por \(x\) para \(y\). A invariância significa que essa regra não distingue posições que são equivalentes pelas simetrias do grafo.

O resultado geral envolve um fator de correção que mede a possível assimetria entre estabilizadores.

Teorema 10.2 (Princípio geral de transporte de massa)
Suponha que \(\Gamma \leq \operatorname {Aut}(X)\), com \(X\) localmente finito, e seja
\[ f:X\times X\longrightarrow [0,\infty ] \]
uma função invariante. Então, para quaisquer \(a,b\in X\),
\[ \sum _{x\in \Gamma b} f(a,x) = \sum _{y\in \Gamma a} f(y,b) \frac{|\Gamma _y b|}{|\Gamma _b y|}. \]
As duas somas podem assumir o valor \(+\infty \).

A única parte menos imediata da prova é a troca dos índices da soma. Vale isolá-la.

Lema 10.3 (Reindexação das órbitas)
Fixe \(a,b\in X\). Para \(z\in \Gamma b\) e \(y\in \Gamma a\),
\[ y\in \Gamma _{z,b}a \qquad \Longleftrightarrow \qquad z\in \Gamma _{y,a}b. \]
Além disso, sempre que essas condições valem,
\[ |\Gamma _{z,b}a|=|\Gamma _b y|. \]

Demonstração ▼

Se \(y\in \Gamma _{z,b}a\), existe \(g\in \Gamma \) tal que

\[ gz=b, \qquad ga=y. \]

Aplicando \(g^{-1}\), obtemos

\[ g^{-1}y=a, \qquad g^{-1}b=z, \]

isto é, \(z\in \Gamma _{y,a}b\). A implicação inversa é a mesma conta com \(g\) e \(g^{-1}\) trocados.

Para a cardinalidade, escolha \(g\) como acima. Pelo Lema 10.1,

\[ |\Gamma _{z,b}a| = |\Gamma _z a| = |\Gamma _b(ga)| = |\Gamma _b y|. \]
Prova do Teorema 10.2 ▼

Fixe \(a,b\in X\). Para \(z\in \Gamma b\), o conjunto \(\Gamma _{z,b}\) é não vazio. Se \(g\in \Gamma _{z,b}\), então, pela invariância de \(f\),

\[ f(a,z)=f(ga,gb)=f(ga,b). \]

Portanto, \(f(y,b)\) tem o mesmo valor para todo \(y\in \Gamma _{z,b}a\). Podemos distribuir o termo \(f(a,z)\) uniformemente sobre esse conjunto:

\[ f(a,z) = \frac{1}{|\Gamma _{z,b}a|} \sum _{y\in \Gamma _{z,b}a} f(y,b). \]

Somando em \(z\in \Gamma b\),

\[ \sum _{z\in \Gamma b}f(a,z) = \sum _{z\in \Gamma b} \frac{1}{|\Gamma _{z,b}a|} \sum _{y\in \Gamma _{z,b}a}f(y,b). \]

Agora aparece a reindexação. Pelo Lema 10.3, o par \((z,y)\) contribui para a soma acima exatamente quando

\[ y\in \Gamma a \qquad \text{e}\qquad z\in \Gamma _{y,a}b. \]

Como todos os termos são não negativos, podemos trocar a ordem das somas por Tonelli:

\[ \sum _{z\in \Gamma b}f(a,z) = \sum _{y\in \Gamma a}f(y,b) \sum _{z\in \Gamma _{y,a}b} \frac{1}{|\Gamma _{z,b}a|}. \]

Fixado \(y\), o mesmo lema mostra que o denominador não depende do \(z\) que aparece na soma:

\[ |\Gamma _{z,b}a|=|\Gamma _b y|. \]

Por outro lado, o Lema 10.1 dá

\[ |\Gamma _{y,a}b|=|\Gamma _y b|. \]

Há, portanto, exatamente \(|\Gamma _y b|\) parcelas, cada uma igual a \(1/|\Gamma _b y|\). Assim,

\[ \sum _{z\in \Gamma _{y,a}b} \frac{1}{|\Gamma _{z,b}a|} = \frac{|\Gamma _y b|}{|\Gamma _b y|}, \]

e obtemos

\[ \sum _{x\in \Gamma b} f(a,x) = \sum _{y\in \Gamma a} f(y,b) \frac{|\Gamma _y b|}{|\Gamma _b y|}. \]

10.3 Unimodularidade

O fator que aparece no princípio geral desaparece quando a ação não distingue, em termos de cardinalidade de órbitas de estabilizadores, o sentido \(x\to y\) do sentido \(y\to x\).

Definição 10.1

Suponha que \(\Gamma \leq \operatorname {Aut}(X)\). Dizemos que a ação de \(\Gamma \) sobre \(X\) é unimodular se

\[ |\Gamma _x y|=|\Gamma _y x| \]

para todos \(x,y\in X\) que pertencem à mesma órbita.

Um grafo transitivo \(X\) é chamado unimodular quando a ação natural de \(\operatorname {Aut}(X)\) sobre \(X\) é unimodular.

Quando a ação é transitiva e unimodular, o princípio geral assume a forma mais familiar.

Corolário 10.4
Suponha que \(\Gamma \leq \operatorname {Aut}(X)\) atue transitivamente e de forma unimodular em \(X\). Se
\[ f:X\times X\longrightarrow [0,\infty ] \]
é invariante, então, para todo \(o\in X\),
\[ \sum _{x\in X}f(o,x) = \sum _{x\in X}f(x,o). \]

Demonstração ▼

Como a ação é transitiva, \(\Gamma o=X\). Aplicando o Teorema 10.2 com \(a=b=o\), obtemos

\[ \sum _{x\in X}f(o,x) = \sum _{x\in X}f(x,o) \frac{|\Gamma _x o|}{|\Gamma _o x|}. \]

Pela unimodularidade, o quociente é igual a \(1\).

O recíproco também é verdadeiro: para ações transitivas, a identidade de transporte de massa caracteriza a unimodularidade.

Teorema 10.5 (Princípio de transporte de massa)
Suponha que \(\Gamma \leq \operatorname {Aut}(X)\) atue transitivamente em \(X\). Então a ação é unimodular se e somente se, para toda função invariante
\[ f:X\times X\longrightarrow [0,\infty ] \]
e todo \(o\in X\), vale
\[ \sum _{x\in X}f(o,x) = \sum _{x\in X}f(x,o). \]

Demonstração ▼

A implicação direta é o Corolário 10.4.

Para a recíproca, suponha que a identidade de transporte de massa valha para toda função invariante. Fixe \(a,b\in X\) e considere a órbita diagonal do par \((a,b)\):

\[ \Gamma (a,b)=\{ (ga,gb):g\in \Gamma \} . \]

Defina

\[ f(x,y)=\mathbf{1}_{\{ (x,y)\in \Gamma (a,b)\} }. \]

A função \(f\) é invariante. Aplicando a identidade de transporte de massa no vértice \(a\), temos

\[ \sum _{y\in X}f(a,y) = \sum _{x\in X}f(x,a). \]

O lado esquerdo conta precisamente os vértices da órbita \(\Gamma _a b\), portanto é igual a \(|\Gamma _a b|\).

Por outro lado, \(f(x,a)=1\) se e somente se existe \(g\in \Gamma \) tal que

\[ ga=x \qquad \text{e}\qquad gb=a. \]

Logo, os possíveis valores de \(x\) formam o conjunto \(\Gamma _{b,a}a\). Como a ação é transitiva, \(\Gamma _{b,a}\neq \emptyset \), e pelo Lema 10.1,

\[ |\Gamma _{b,a}a|=|\Gamma _b a|. \]

Consequentemente,

\[ |\Gamma _a b|=|\Gamma _b a|. \]

Como \(a\) e \(b\) são arbitrários, a ação é unimodular.

10.4 Forma aleatória do princípio

Nas aplicações probabilísticas, a quantidade de massa enviada depende da própria configuração aleatória. Essa é a forma que será usada no capítulo seguinte.

Suponha que \(\Omega \) seja uma configuração aleatória cuja distribuição é invariante sob uma ação transitiva e unimodular de \(\Gamma \) em \(X\). Seja

\[ F:X\times X\times \Omega \longrightarrow [0,\infty ] \]

uma regra de transporte satisfazendo a equivariância

\[ F(gx,gy,g\omega )=F(x,y,\omega ) \]

para todo \(g\in \Gamma \).

Defina

\[ f(x,y)=\mathbb {E}[F(x,y,\Omega )]. \]

Pela invariância da lei de \(\Omega \), a função \(f\) é invariante. Portanto, pelo Teorema 10.5 e pelo teorema de Tonelli,

\[ \mathbb {E}\left[\sum _{y\in X}F(o,y,\Omega )\right] = \mathbb {E}\left[\sum _{x\in X}F(x,o,\Omega )\right]. \]

Em palavras: a massa esperada enviada pela origem é igual à massa esperada recebida pela origem. Essa formulação permite transformar propriedades globais de uma configuração aleatória em identidades locais, e será a principal ferramenta do próximo capítulo.