Uma visão aproximada revela o ponto de ‘fusão’ de um gráfico infinito | Revista Quanta

Em 2008, o matemático Oded Schramm morreu num acidente de caminhada nas montanhas Cascade, cerca de 50 quilômetros a leste de Seattle. Embora tivesse apenas 46 anos, ele construiu áreas inteiramente novas da matemática.

“Ele era um matemático fantástico”, disse Itai Benjamini, matemático do Instituto Weizmann de Ciência e amigo e colaborador de Schramm. “Extremamente criativo, extremamente elegante, extremamente original.”

As perguntas que ele fez ainda ultrapassam as fronteiras da teoria das probabilidades e da física estatística. Muitas dessas questões dizem respeito a estruturas matemáticas que têm uma transição de fase – uma mudança macroscópica repentina, como o derretimento do gelo em água. Assim como diferentes materiais têm diferentes pontos de fusão, as transições de fase das estruturas matemáticas também variam.

Schramm conjecturou que a transição de fase num processo chamado percolação pode ser estimada usando apenas uma visão aproximada do sistema – chamada perspectiva local – para muitas estruturas matemáticas importantes. Diminuir totalmente o zoom e olhar para tudo não alterará significativamente o cálculo. Nos últimos 15 anos, os matemáticos destrincharam pequenos pedaços da conjectura, mas até agora não foram capazes de resolvê-la completamente.

Em um artigo do pré-impressão publicada em outubro, Tom Hutchcroft do Instituto de Tecnologia da Califórnia e seu aluno de doutorado Filipe Easo provou a conjectura de localidade de Schramm. A sua prova baseia-se em ideias importantes da teoria das probabilidades e de outras áreas da matemática, que combinaram de forma inteligente.

“É um artigo notável. É um acúmulo de trabalho longo”, disse Benjamini.

Clusters infinitos

A palavra “percolação” referia-se originalmente ao movimento de fluido através de um meio poroso, como a água fluindo através de borra de café ou óleo escoando através de rachaduras em uma rocha.

Em 1957, os matemáticos Simon Ralph Broadbent e John Michael Hammersley desenvolveram um modelo matemático deste processo físico. Nas décadas seguintes, este modelo tornou-se um objeto de estudo por si só. Os matemáticos estudam a percolação porque ela atinge um equilíbrio importante: a configuração é simples, mas apresenta características complexas e intrigantes.

“É uma espécie de modelo canônico para matemáticos”, disse Hutchcroft. “Você pode pensar nas coisas visualmente. Isso torna muito bom trabalhar com ele.”

A percolação começa com um gráfico, que é uma coleção de vértices (pontos) que podem ser conectados por arestas (linhas). Um dos exemplos mais simples é uma grade quadrada, com vértices alinhados para formar os cantos dos quadrados e arestas conectando alguns deles.

Pouco antes de sua morte, Schramm conjecturou que o teorema de Grimmett e Marstrand poderia ser generalizado. Ele pensava que o limiar de percolação é determinado inteiramente pela perspectiva aproximada, ou “microscópica”, para uma grande classe de gráficos conhecidos como gráficos transitivos.

Em 2009, Benjamini, Asaf Nachmias e Yuval Peres provou A conjectura de localidade de Schramm, como é conhecida agora, para um tipo específico de grafo transitivo que se assemelha a uma árvore. Schramm, no entanto, postulou que isso seria válido para todos os grafos transitivos (com exceção dos grafos unidimensionais).

Em um gráfico transitivo, todos os vértices parecem semelhantes. Uma grade bidimensional é um exemplo. Se você escolher dois vértices quaisquer, sempre poderá encontrar uma simetria que mova um vértice para o outro.

Esta relação vale para qualquer grafo transitivo. Devido a essas simetrias, se você aumentar o zoom e observar quaisquer duas partes de tamanhos iguais de um gráfico transitivo, elas terão a mesma aparência. Por esta razão, Schramm acreditava que a perspectiva aproximada era suficiente para permitir aos matemáticos calcular o limiar de percolação para todos os gráficos transitivos.

Os gráficos transitivos podem assumir muitas formas e formas. Podem ser uma grade simples, composta por quadrados, triângulos, hexágonos ou alguma outra forma. Ou podem formar um objeto mais complexo, como uma “árvore 3-regular”, onde um ponto central se conecta a três vértices, e cada vértice então se ramifica para criar dois novos ad infinitum, cujos primeiros passos são vistos aqui:

A variedade de gráficos transitivos contribuiu para a dificuldade de provar a conjectura de localidade de Schramm. Nos 15 anos entre a conjectura de Schramm e a prova de Easo e Hutchcroft, vários grupos de matemáticos provaram a conjectura para tipos específicos de gráficos, mas as suas ideias nunca se estenderam ao caso geral.

“O espaço de todas as geometrias possíveis é muito vasto e há sempre coisas estranhas à espreita”, disse Hutchcroft.

Ampliando a lente

Easo e Hutchcroft não procuravam inicialmente uma solução para a conjectura de localidade de Schramm, que se aplica a grafos infinitos. Em vez disso, eles estavam estudando a percolação em gráficos finitos. Mas eles tiveram uma ideia que de repente desviou sua atenção para a conjectura.

“Criamos essa nova ferramenta e pensamos, ah, isso parece o tipo de coisa que poderia ser útil para atacar localidades”, disse Easo.

Para provar a conjectura, precisavam de mostrar que a perspectiva microscópica proporciona uma imagem precisa do limiar de percolação. Ao visualizar apenas parte de um gráfico e observar um grande cluster conectado, você pode assumir que o gráfico tem um cluster infinito e, portanto, está acima do limite de percolação. Easo e Hutchcroft decidiram provar isso.

Eles confiaram em uma técnica que pode ser considerada como “ampliar as lentes”. Comece em um único vértice. Em seguida, diminua o zoom para visualizar todos os vértices que estão a apenas uma aresta de distância no gráfico original. Na grade quadrada, agora você poderá ver cinco vértices no total. Amplie a lente novamente para ver todos os vértices a uma distância de duas arestas e, em seguida, a uma distância de três arestas, quatro arestas e assim por diante.

Easo e Hutchcroft definem o mostrador que determina quantos links existem perto de onde viram um grande aglomerado. Eles então ampliaram a lente, observando cada vez mais bordas se reunindo em seu grande aglomerado. Ao fazerem isso, tiveram que aumentar a probabilidade de presença de links, o que torna mais fácil mostrar que o gráfico tem um grande componente conectado. Este é um ato de equilíbrio delicado. Eles precisavam ampliar o campo de visão com rapidez suficiente e adicionar links com lentidão suficiente para revelar o gráfico infinito completo sem alterar drasticamente a posição do mostrador.

Eles conseguiram mostrar que os aglomerados grandes crescem mais rápido do que os menores, de modo que, como disse Easo, “seu aglomerado cresce cada vez mais rápido à medida que fica cada vez maior, como quando você está rolando uma bola de neve”.

Para a grade quadrada, a contagem de vértices cresce relativamente lentamente. É aproximadamente a largura da sua lente ao quadrado. Após 10 etapas, você encontrará cerca de 100 vértices. Mas uma árvore 3 regular cresce exponencialmente mais rápido - aproximadamente 2 elevada à potência da largura da sua lente. Após 10 etapas, você verá aproximadamente 1,024 vértices. A ilustração abaixo mostra como a árvore 3-regular é muito maior depois de apenas sete etapas, embora a grade quadrada tenha mais vértices no início. Em geral, os gráficos podem ter diferentes taxas de crescimento em diferentes escalas — eles podem começar rápido e depois desacelerar.

Em 2018, Hutchcroft usei uma ideia semelhante para provar a conjectura de localidade para gráficos de crescimento rápido como a árvore 3-regular. Mas não funcionou para gráficos de crescimento lento, como a grelha quadrada, ou para gráficos que crescem a uma velocidade intermédia, não cumprindo nem os critérios matemáticos para crescimento rápido nem os de crescimento lento.

“É aqui que as coisas ficam realmente frustrantes por cerca de três anos”, disse Hutchcroft.

Estrutura versus Expansão

Para gráficos que misturam taxas de crescimento em diferentes escalas, é necessário usar uma variedade de técnicas.

Um fato muito útil é que, como explicou Easo, “se um gráfico parece ter crescimento lento em alguma escala, então ele fica preso”. Continuará a crescer lentamente em escalas maiores. Como os gráficos de crescimento lento têm uma estrutura adicional determinada por um ramo da matemática chamado teoria dos grupos, também se sabia que, se você diminuir o zoom o suficiente, os gráficos de crescimento lento exibiriam uma geometria que é matematicamente domesticada.

Em 2021, Sébastien Martineau da Universidade Sorbonne em Paris, trabalhando com Daniel Contreras e Vicente Tassion da ETH Zurich, conseguiu usar esta propriedade para provar a conjectura de localidade de Schramm para gráficos que eventualmente crescem lentamente.

Neste ponto, os dois grupos de matemáticos tinham abordado com sucesso a conjectura a partir de direções diferentes: crescimento rápido e crescimento lento. Mas isso deixou lacunas consideráveis. Por um lado, existe uma categoria de crescimento intermédio que não foi abrangida pela técnica de Easo e Hutchcroft ou pela prova de Contreras, Martineau e Tassion. Outro problema era que os argumentos ainda não se aplicavam a gráficos com taxas de crescimento variáveis ​​– apenas aqueles que permaneciam rápidos ou lentos. Para que o argumento de Contreras, Martineau e Tassion fosse aplicado a gráficos arbitrários, não bastava que a geometria eventualmente parecesse inofensiva quando você diminuísse o zoom, explicou Easo: “Precisamos que ela pareça inofensiva agora, perto da escala atual”.

No meio do nada

Os gráficos transitivos de crescimento intermediário são muito misteriosos. Os matemáticos nunca encontraram um exemplo de gráfico transitivo cujo crescimento se enquadrasse nesta faixa. É possível que eles nem existam. Mas os matemáticos não provaram que eles não existem, por isso qualquer prova completa da conjectura da localidade de Schramm deve abordá-los. Para aumentar o desafio, Easo e Hutchcroft precisavam abordar gráficos que poderiam ter crescimento intermediário apenas brevemente em uma escala de comprimento específica, mesmo que crescessem mais rápido ou mais devagar quando você aumenta ou diminui o zoom.

Easo e Hutchcroft passaram grande parte do ano passado trabalhando para estender seus resultados para aplicá-los a gráficos que não foram cobertos por nenhum dos métodos anteriores.

Primeiro, modificaram a técnica de 2018 que Hutchcroft aplicou a gráficos de crescimento rápido para trabalhar em gráficos que alteram os níveis de crescimento em diferentes escalas. Abordaram então o caso do crescimento lento, em um artigo de 27 páginas eles compartilharam em agosto que expandiram o trabalho em Contreras, Martineau e Tassion. Finalmente, em sua pré-impressão de outubro, eles desenvolveram outro argumento usando a teoria dos passeios aleatórios — linhas que se movem aleatoriamente no espaço — para lidar com o caso de crescimento intermediário. Com a tricotomia completa, eles provaram a conjectura de localidade de Schramm.

“Tivemos que usar tudo o que sabíamos para resolver o problema”, disse Hutchcroft.

A solução dá aos matemáticos uma visão melhor do que acontece acima do limite de percolação, onde a chance de um cluster infinito é de 100%, e abaixo dele, onde a chance é de 0%. Mas os matemáticos ainda estão perplexos com o que acontece exatamente no limiar da maioria dos gráficos, incluindo a grade tridimensional. “Essa é provavelmente a questão em aberto mais famosa e básica da teoria da percolação”, disse Russell Lyons da Universidade de Indiana.

A grade bidimensional é um dos poucos casos em que os matemáticos provaram o que acontece exatamente no limiar: aglomerados infinitos não se formam. E depois que Grimmett e Marstrand provaram uma versão da conjectura de localidade para grandes lajes, Grimmett e colaboradores mostraram que se você cortar uma grade 3D ao meio horizontalmente, criando um piso, e ajustar o mostrador exatamente no limite de percolação, nenhum aglomerado infinito aparecerá. O seu resultado sugere que a grelha tridimensional completa, tal como a sua contraparte bidimensional, pode não ter um aglomerado infinito no limiar de percolação.

Em 1996, Benjamini e Schramm conjecturado que a chance de encontrar um cluster infinito bem no limite é zero para todos os gráficos transitivos — assim como é para a grade 2D ou para a grade 3D cortada ao meio. Agora que a conjectura da localidade foi resolvida, a compreensão do que acontece exatamente no ponto de transição pode estar um pouco mais próxima.

Correção: 18 de dezembro de 2023
O número de nós dentro de n links de um nó inicial em um gráfico 3-regular cresce aproximadamente 2ⁿ, não 3ⁿ como este artigo declarou originalmente. O artigo foi corrigido.

Quanta está realizando uma série de pesquisas para melhor atender nosso público. Pegue nosso pesquisa com leitores de matemática e você estará inscrito para ganhar de graça Quanta mercadoria.