Subgrafos Monocromáticos e os Limites de Grafos (Graphons)

Nada nos impede de procurar padrões maiores que uma aresta. Fixe um grafo pequeno $H$ — um triângulo ($K_3$), uma estrela, um ciclo — e conte quantas cópias de $H$ em $G_n$ ficaram inteiramente da mesma cor. Esse número é $T(H, G_n)$, o contador de subgrafos monocromáticos.

A primeira pergunta natural é: quanto esperamos contar, em média? A resposta é elegante:

onde $N(H, G_n)$ é o número de cópias de $H$ no grafo $G_n$ (sem falar de cores) e $|V(H)|$ é o número de vértices de $H$. Em palavras: o valor esperado é o total de cópias vezes a probabilidade de uma cópia específica sair monocromática.

Considere o grafo de amizade de uma rede social e “colora” cada pessoa com o seu dia de aniversário: são $c = 365$ cores. Uma aresta monocromática é exatamente um par de amigos que fazem aniversário no mesmo dia. Assim,

é a probabilidade de haver alguma coincidência de aniversário entre amigos — uma variante do célebre problema do aniversário, que surpreende todo mundo: basta um grupo de 23 pessoas (no grafo completo $K_{23}$, onde todos se conhecem) para que a chance de coincidência passe de $50\%$.

A generalização é natural: multi-colisões, em que $r$ pessoas compartilham o mesmo aniversário, correspondem a cliques monocromáticos $T(K_r, G_n)$. E o assunto é sério: o artigo menciona aplicações em segurança de funções hash (uma “colisão de hash” é um aniversário repetido, e ataques de aniversário exploram exatamente isso), em testes de hipóteses para distribuições discretas e no estudo de coincidências em geral.

Um problema clássico da estatística: observamos duas amostras e queremos testar

isto é, decidir se as duas amostras vêm da mesma distribuição, sem assumir que as distribuições têm algum formato conhecido (por isso “não-paramétrico”).

A estratégia baseada em grafos é engenhosa. Empilham-se as duas amostras em um único conjunto de pontos e constrói-se um grafo geométrico sobre eles, ligando pontos próximos — por exemplo a árvore geradora mínima do teste de Friedman–Rafsky, ou grafos de vizinhos mais próximos. Os rótulos das amostras (amostra 1 ou amostra 2) funcionam como cores: aqui $c = 2$.

• H₀ Se as amostras vêm da mesma distribuição, os pontos das duas amostras estão bem misturados no espaço: arestas ligam frequentemente pontos de amostras diferentes, e há poucas arestas monocromáticas.
• H₁ Se as distribuições diferem, cada amostra ocupa sua própria região: pontos próximos tendem a vir da mesma amostra, as arestas “bicolores” ficam raras e as arestas monocromáticas abundam.

Logo, rejeita-se $H_0$ quando $T(K_2, G_n)$ é grande demais. E para calibrar o que é “grande demais”, é preciso entender a distribuição nula de $T(K_2, G_n)$ — ou seja, estudar exatamente o contador monocromático com $c = 2$ que definimos na Parte I. Teoria de grafos aleatórios coloridos a serviço da estatística.

No caso de duas cores ($c = 2$), troque os rótulos de cor por variáveis $Y_u \in \{-1, +1\}$ independentes com $\mathbb{P}(Y_u = 1) = \mathbb{P}(Y_u = -1) = 1/2$ — as chamadas variáveis de Rademacher. Um truque algébrico simpático, $\mathbf{1}\{X_u = X_v\} = \tfrac{1}{2}(1 + Y_u Y_v)$, revela uma identidade surpreendente:

Do lado direito temos uma forma quadrática aleatória — um “caos quadrático de Rademacher”. Estruturas idênticas aparecem em vários lugares:

• Física O Hamiltoniano do modelo de Ising — o modelo clássico de magnetismo, em que “spins” $\pm 1$ interagem ao longo das arestas de uma rede — tem exatamente a forma $\sum_{u,v} a_{uv}\, Y_u Y_v$.
• Comb. A teoria de Ramsey estuda justamente subestruturas monocromáticas inevitáveis em colorações de grafos.
• Estat. Formas quadráticas desse tipo aparecem em testes de independência e no estudo de esquemas de urna e estatísticas de coincidência.

Moral da história: entender as flutuações de $T(H, G_n)$ é entender um objeto que a física, a combinatória e a estatística já encontraram, cada uma por seu caminho.

Um graphon é uma função simétrica e mensurável

em que $W(x,y)$ se interpreta como a probabilidade de conexão entre os “pontos” $x$ e $y$. O intervalo $[0,1]$ representa o “continuum” de vértices no limite $n \to \infty$.

O caminho de volta, do discreto ao contínuo, é feito pelo graphon empírico $W^{G_n}$: divide-se o quadrado $[0,1]^2$ em $n^2$ quadradinhos de lado $1/n$ e atribui-se ao quadradinho $(i,j)$ o valor $1$ se $(i,j)$ é aresta de $G_n$ e $0$ caso contrário. É exatamente a matriz de adjacência desenhada como uma função escada — a “imagem de pixels” da nossa analogia.

Para um grafo pequeno $F$ (digamos, um triângulo), a densidade de homomorfismo $t(F, G)$ mede a frequência com que $F$ aparece em $G$: é a probabilidade de que um mapa aleatório dos vértices de $F$ para os vértices de $G$ envie cada aresta de $F$ em uma aresta de $G$. No mundo contínuo, a soma vira integral:

O exemplo a se guardar é o triângulo $F = K_3$: o produto sobre as arestas tem três fatores, e a fórmula vira a integral tripla

Leia assim: sorteie três pontos $x, y, z$ uniformemente em $[0,1]$; a integral é a probabilidade de que todas as três conexões do triângulo se realizem. Cada fator $W$ cuida de uma aresta.

Dizemos que $G_n$ converge para $W$ quando as densidades de todos os padrões finitos se estabilizam:

A teoria dos limites de grafos, desenvolvida por Lovász, Szegedy e colaboradores, mostra que essa noção equivale a ser uma sequência de Cauchy na distância de corte, definida a partir da norma de corte:

A intuição é a de um fiscal de densidades: escolha qualquer bloco de vértices $A$ e qualquer bloco $B$ e meça a massa de conexões entre eles. A norma de corte é a pior discrepância possível entre blocos. Se dois graphons estão próximos nessa norma, nenhum teste do tipo “compare a densidade entre estes dois grupos” consegue distingui-los. (Tecnicamente, a distância de corte $\delta_\square$ ainda permite reetiquetar os vértices, ou seja, aplicar uma permutação de $[0,1]$ que preserve medida — o grafo limite não depende da ordem em que listamos os vértices.)

Em grafos densos, $T(H, G_n)$ centrado e devidamente normalizado não converge, em geral, para uma Gaussiana. O limite é a soma de duas componentes independentes:

• (i) uma variável Gaussiana $Z$, que herda as flutuações “lineares” — grosso modo, o efeito de cada vértice individualmente através do seu grau;
• (ii) uma soma de variáveis qui-quadrado (centradas), que pode ser escrita como uma integral estocástica de Wiener–Itô dupla $$\int_{[0,1]^2} W_H(x,y)\, dB_x\, dB_y,$$ em que $(B_x)_{x \in [0,1]}$ é um movimento Browniano e os pesos vêm do espectro do kernel condicional de 2 pontos $W_H$, um operador construído a partir do graphon limite $W$ e do padrão $H$.

Mais precisamente: se $\lambda_1 \geq \lambda_2 \geq \cdots$ são os autovalores do operador integral associado a $W_H$, a segunda componente tem a forma $\sum_{k \geq 1} \lambda_k\, (\xi_k^2 - 1)$, com $\xi_k$ Gaussianas padrão independentes. Cada $\xi_k^2$ é uma qui-quadrado com 1 grau de liberdade — daí o nome.

Para o caso mais simples, $H = K_2$ (arestas monocromáticas), o kernel é apenas o próprio graphon (vezes dois):

Quando a componente Gaussiana domina, o limite é normal; quando os autovalores $\lambda_k$ são relevantes, a cauda qui-quadrado aparece e o limite fica assimétrico, com cauda pesada à direita — nada parecido com o sino da Gaussiana.

Como decidir, na prática, se o limite é Gaussiano? Há um critério notavelmente simples, na linha do chamado fenômeno do quarto momento: normalizando $T(K_2, G_n)$ para ter média $0$ e variância $1$,

onde $\widehat{T}$ denota a versão padronizada. O número $3$ não é mágico: é o quarto momento de uma Gaussiana padrão, $\mathbb{E}[Z^4] = 3$. Se o quarto momento converge para $3$, o limite só pode ser Gaussiano; se converge para algo maior, há componente qui-quadrado no limite.

O artigo de Andrade & Bhattacharya dá um passo além: em vez de uma única rede, considera várias camadas de grafos sobre os mesmos vértices — uma rede multiplex. Pense nas mesmas pessoas conectadas simultaneamente por laços de amizade, de trabalho e de família: três camadas, um único conjunto de vértices, uma única coloração aleatória compartilhada por todas as camadas.

Como as cores são as mesmas em todas as camadas, os contadores monocromáticos $T(H_1, G_n^{(1)}), T(H_2, G_n^{(2)}), \ldots$ de camadas diferentes são dependentes. A contribuição central do artigo é derivar a distribuição limite conjunta desses contadores, provando convergência em uma métrica de corte conjunta (várias camadas vistas como um único objeto). O limite tem a forma:

• Z uma Gaussiana multivariada, independente da outra componente, cuja matriz de covariância codifica as sobreposições entre camadas;
• $\chi^2$ uma soma de integrais estocásticas bivariadas — mas todas tomadas em relação ao mesmo movimento Browniano $(B_x)$. É esse compartilhamento do ruído que captura a dependência entre as camadas: as flutuações quadráticas de todas as camadas “ouvem” o mesmo Browniano, porque a coloração aleatória é a mesma para todas.

Como se prova um teorema desses? A estratégia, explicada por alto, tem dois movimentos:

• 1. Princípio de invariância: as variáveis de cor $X_u$ (discretas, uniformes em $c$ cores) podem ser substituídas por variáveis Gaussianas com a mesma média, variância e covariância, sem alterar a distribuição limite. É uma versão sofisticada do teorema central do limite: no limite, só os dois primeiros momentos importam, então podemos trocar uma distribuição complicada por uma conveniente. (É a mesma filosofia por trás do método de Lindeberg e dos “universality principles” em matrizes aleatórias.)
• 2. Só o quadrático sobrevive: depois da troca, expande-se o contador em “caos” de ordens crescentes — termos lineares, quadráticos, cúbicos etc. Na escala densa, os termos de ordem $\geq 3$ se tornam desprezíveis após a normalização, e restam apenas o termo linear (que vira a Gaussiana $Z$) e o quadrático (que vira a soma de qui-quadrados / integral de Wiener–Itô).

É por isso que o limite tem exatamente duas personalidades: uma linear (Gaussiana) e uma quadrática (qui-quadrado). A estrutura do graphon $W$ e do padrão $H$ determinam, via kernel $W_H$, o peso de cada uma.

• Art. M. D. Andrade & B. B. Bhattacharya, Monochromatic Subgraphs in Randomly Colored Dense Multiplex Networks, arXiv:2501.07821 (2025) — o artigo que inspirou esta apostila.
• Livro L. Lovász, Large Networks and Graph Limits, AMS Colloquium Publications (2012) — a referência clássica sobre graphons, densidades de homomorfismo e a distância de corte.

Boa leitura — e da próxima vez que dois amigos fizerem aniversário no mesmo dia, lembre-se: você acabou de observar um subgrafo monocromático.