MatemáticaPré-publicaçãoTeoria4 min de leitura

REDES ALEATÓRIAS DEIXAM DE SER COLORÍVEIS NUMA DENSIDADE FIXA

Pegue um grafo — pontos unidos por ligações — e uma caixa de cores. Uma coloração própria com q cores dá a cada ponto uma de q cores de modo que dois pontos ligados nunca tenham a mesma. Com poucas ligações, isso é fácil. Com muitas, torna-se impossível.

Agora construa o grafo ao acaso: n pontos, cada par ligado de forma independente com uma pequena probabilidade, de modo que um ponto tenha em média d vizinhos. À medida que d cresce, o grafo aleatório passa de “quase certamente colorível com q cores” para “quase certamente não colorível”. Onde exatamente acontece a virada? Essa pergunta, para qualquer número fixo de cores q a partir de três, é o tema de um novo artigo de Gaia Carenini, da Universidade de Cambridge.

Uma virada que poderia oscilar

Num artigo de 1999 que consta da bibliografia, Achlioptas e Friedgut provaram que a transição é abrupta: para cada tamanho n, existe um grau médio crítico d_q(n) tal que, um pouco abaixo dele, o grafo é quase certamente colorível e, um pouco acima, quase certamente não. A janela em que a virada acontece encolhe até desaparecer.

Mas isso deixava uma brecha. Nada impedia que o próprio valor crítico oscilasse à medida que os grafos ficavam maiores — num lugar para grafos de um tamanho, num lugar um pouco diferente para grafos maiores, sem nunca se fixar. A conjectura de convergência de Achlioptas–Friedgut afirma que isso não acontece: para cada q, existe uma única constante d_q, abaixo da qual os grafos aleatórios são coloríveis e acima da qual não são.

O que os físicos previam

A física estatística tinha uma imagem do que acontece. À medida que ligações são adicionadas, as colorações válidas se agrupam em aglomerados (clusters): as colorações de um mesmo aglomerado se parecem entre si, enquanto dois aglomerados diferem em muitos pontos. Depois, numa etapa chamada condensação, um punhado de grandes aglomerados concentra uma parte substancial de todas as colorações — e só mais tarde o conjunto de colorações fica vazio. Essa organização explica por que os argumentos de contagem têm dificuldade perto do limiar.

Para muitas cores, trabalhos anteriores já tinham encerrado o limiar num intervalo estreito: ele fica entre cerca de 2q log q − log q − 2 log 2 e 2q log q − log q − 1, uma faixa de largura 2 log 2 − 1 à medida que q cresce. Mas “estreito” não é “fixo” e, para números pequenos de cores, como três, a questão continuava em aberto.

Um problema gêmeo, atacado primeiro

A coloração tem um gêmeo: a satisfatibilidade, o problema de escolher valores verdadeiro ou falso para variáveis de modo que todas as restrições lógicas de uma lista aleatória sejam satisfeitas. Ali também se sabia que existia um limiar abrupto, sem prova de que ele se fixa. Num relatório de 2026 citado no artigo, Carenini anunciou uma prova de que ele se fixa, para todo comprimento de restrição a partir de três, mostrando que a janela de transição é muito estreita. O novo artigo adapta esse argumento à coloração.

Pares congelados juntos

A prova avança por uma cadeia de reduções. Adicionando ligações aleatórias uma a uma, seja H o momento em que o grafo deixa de ser colorível. Se H varia pouco de um grafo aleatório para outro — dentro de uma janela de cerca de n/(log n)² ligações —, então o limiar tem de se fixar. Uma desigualdade clássica transforma isso numa pergunta sobre o último grafo colorível: em média, a quantas novas ligações aleatórias ele sobrevive?

Aqui entra a noção-chave: os pares congelados. Dois pontos formam um par congelado quando toda coloração válida lhes dá a mesma cor. Uma nova ligação é fatal exatamente quando une um par assim. Pontos isolados não podem ficar congelados numa cor específica, já que permutar as cores sempre produz outra coloração válida; o que fica forçado é uma relação entre dois pontos. Carenini acompanha como essas classes congeladas crescem à medida que ligações são adicionadas, removendo uma ligação ou um ponto inteiro e observando as escolhas que reaparecem. As estimativas mostram que o último grafo colorível não pode sobreviver por muito tempo, o que estreita a janela o suficiente para provar a conjectura.

O que continua desconhecido

O teorema diz que o limiar d_q existe para todo q ≥ 3. Ele não diz onde fica: o artigo não dá nenhum valor para ele, nem mesmo para três cores. O artigo é uma pré-publicação de autoria única e não foi revisado por pares. Ele termina com uma breve declaração de que nenhum de seus argumentos matemáticos foi gerado por um grande modelo de linguagem.