Um pequeno salto muito grande na teoria dos grafos

Em 15 de março, anúncios de seminários intrigantes causaram rebuliço no campo da combinatória, o estudo matemático da contagem. Três colaboradores planejaram fazer palestras coordenadas no dia seguinte. Julian Sahasrabudhe abordaria matemáticos em Cambridge, Inglaterra, enquanto Simon Griffiths daria a notícia no Rio de Janeiro e Marcelo Campos em São Paulo. Todas as três palestras exibiam títulos idênticos e resumos enigmáticos de duas frases referenciando “progressos recentes em um antigo problema de Erdős”. Enquanto Paul Erdős, um matemático húngaro que morreu em 1996, posou centenas de problemas durante sua carreira, combinatoristas rapidamente adivinharam o assunto específico sobre o qual o trio planejava falar. Rumores circulavam sobre algo chamado número de Ramsey, uma das quantidades mais difíceis de calcular em toda a matemática.

Os números de Ramsey geraram toda uma disciplina chamada teoria de Ramsey, que procura padrões inescapáveis ​​em uma grande variedade de sistemas.

Por exemplo, digamos que você tente espalhar todos os números inteiros entre vários baldes e deseja evitar a colocação de sequências de números espaçados uniformemente em qualquer um dos baldes. A teoria de Ramsey mostra que você falhará (a menos que tenha infinitos baldes). A teoria pode ser aplicada a quase tudo que você possa contar. Sua lição central é que “você não pode criar um sistema completamente caótico”, disse Benny Sudakov, matemático do Instituto Federal Suíço de Tecnologia de Zurique.

O número de Ramsey quantifica quão grande um exemplo paradigmático deve ser antes que padrões particulares surjam inevitavelmente. Mas, apesar de sua centralidade, ninguém foi capaz de calcular o número de Ramsey para todos, exceto o instâncias mais simples. O melhor que eles conseguiram fazer foi encontrar limites (ou limites) para o que poderia ser. Mesmo assim, o limite superior estabelecido pela primeira vez por Erdős e um colaborador quase um século atrás mal havia se movido.

Então, nos seminários de 15 de março e em um artigo publicado mais tarde naquela noite, os pesquisadores anunciaram que haviam melhorado o limite superior do número de Ramsey em uma quantidade exponencial.

“Fiquei sem chão”, disse Yuval Wigderson, um matemático da Universidade de Tel Aviv, ao ouvir sobre o novo resultado. “Eu estava literalmente tremendo por meia hora a uma hora.”

As linhas do partido

A teoria de Ramsey geralmente faz perguntas sobre números inteiros ou sobre gráficos. Um gráfico, neste contexto, refere-se a coleções de pontos chamados nós, conectados por linhas chamadas arestas, que podem ter propriedades como comprimento ou — como no caso dos números de Ramsey — cor.

Um grafo completo é complicado e simples – cada nó está conectado a todos os outros nós. O número de Ramsey descreve quantos nós um grafo completo deve conter para ser forçado a ter uma estrutura particular. Digamos que as arestas de um gráfico completo sejam atribuídas a uma das duas cores: vermelho ou azul. E digamos que você tente colorir as arestas de forma a evitar conectar um grupo de nós com arestas da mesma cor. Em 1930, Frank Ramsey provou que, se um gráfico é grande o suficiente, torna-se impossível evitar a criação do que os matemáticos chamam de clique monocromático – um grupo de nós cujas arestas comuns são todas vermelhas ou todas azuis.

Qual deve ser o tamanho exato de um gráfico antes que um clique monocromático seja forçado a surgir? A resposta depende do tamanho do clique. Ramsey mostrou que existe um número, agora chamado de número de Ramsey, que representa o número mínimo de nós para os quais deve existir um clique monocromático de um determinado tamanho, independentemente de como as arestas são coloridas.

Mas o tamanho do número de Ramsey é difícil de definir. Em 1935, cinco anos depois que Ramsey mostrou que ele existe, Erdős e George Szekeres forneceram um limite superior novo e mais rígido sobre o tamanho do número de Ramsey para um clique de um determinado tamanho. Mas, desde então, os matemáticos mal conseguiram melhorar os cálculos de Erdős e Szekeres.

Para ter uma melhor intuição do que isso significa, considere um exemplo clássico, no qual os nós representam convidados em uma festa. Pinte a borda entre quaisquer dois convidados de vermelho se eles já se conheceram antes e de azul se não se conheceram. Você pode escolher o tamanho de panelinha que quiser - convide pessoas suficientes para a festa e não pode evitar convidar um grupo de pessoas que se conhecem (uma panelinha em vários sentidos da palavra) ou convidar um grupo de pessoas que nunca conheci antes.

“A coisa mais simples que você pode ter em um gráfico é um clique monocromático”, disse Maria chudnovsky, um matemático da Universidade de Princeton. “É incrível que em cada grande gráfico você possa encontrar um grande desses. Não está completamente claro.

Os primeiros números de Ramsey são relativamente simples de calcular. Digamos que você queira saber o tamanho do menor gráfico que deve inevitavelmente conter um clique de tamanho dois, ou R(2) para os matemáticos. Como um grafo completo com dois nós é apenas dois nós conectados por uma aresta, e essa aresta deve ser vermelha ou azul, R(2) é 2. Mais geralmente, R(k), ou o número de Ramsey de k, é o número mínimo de nós além do qual um grafo não pode evitar conter um clique de tamanho k.

Não é tão difícil mostrar que o número de Ramsey para um clique de tamanho 3, ou R(3), é 6 (veja o gráfico). Mas não foi até 1955 que R(4) foi fixado em 18. R(5) permanece desconhecido - é pelo menos 43 e não maior que 48. Embora esses números sejam pequenos, peneirar todas as cores possíveis está fora de questão da questão, disse David Conlon, do Instituto de Tecnologia da Califórnia. Considere o número de cores em um grafo completo com 43 nós. “Você tem 903 arestas; cada um deles pode ser colorido de duas maneiras”, explicou. “Então você ganha 2⁹⁰³, que é astronomicamente grande.”

À medida que o tamanho do grupo aumenta, a tarefa de descobrir o número de Ramsey fica cada vez mais difícil. Erdős brincou que uma guerra total com alienígenas matematicamente exigentes seria mais fácil do que tentar descubra R(6), que está em algum lugar entre 102 e 165. A faixa de incerteza cresce rapidamente: De acordo com estimativas compiladas por Stanisław Radziszowski, R(10) pode ser tão pequeno quanto 798 e tão grande quanto 23,556. Mas os objetivos dos matemáticos vão muito além do número de Ramsey de 10. Eles querem uma fórmula que dê uma boa estimativa de R(k), mesmo — ou especialmente — quando k é extremamente grande.

“Não conheço uma pessoa em combinatória que não tenha pensado sobre esse problema pelo menos um pouco”, disse Wigderson. “Esse problema é, eu acho, muito especial.”

Ordem no Tribunal

Frank Ramsey era uma figura eclética e brilhante que morreu aos 26 anos. Poucas semanas antes de sua morte, o Anais da London Mathematical Society publicado o papel em que ele introduziu os números de Ramsey. Aquele trabalho nem era sobre gráficos, mas sobre um problema de lógica matemática. Ramsey provou que uma afirmação que satisfaça certas condições tem que ser verdadeira pelo menos parte do tempo. Uma dessas condições era que houvesse um grande “universo” de cenários para testar a afirmação. Como trampolim para esse resultado, Ramsey mostrou que o número de Ramsey é finito.

Cinco anos depois, Erdős e Szekeres mostraram que o número de Ramsey de k é menor que 4^k. E 12 anos depois disso, Erdős mostrou que é maior do que $latex sqrt{2}^k$. Para fazer isso, ele calculou as chances de um grafo com arestas coloridas aleatoriamente conter um clique monocromático. Essa técnica “probabilística” tornou-se massivamente influente na teoria dos grafos. Ele também prendeu R(k) entre duas traves de crescimento exponencial: $latex sqrt{2}^k$ e $latex 4^k$.

Com o passar das décadas, vários matemáticos tentaram diminuir a diferença entre os possíveis valores do número de Ramsey. Alguns tiveram sucesso: em 1975, Joel Spencer dobrou o limite inferior. E uma série de artigos de Conlon, André Thomason e Ashwin Sah empurrou para baixo o limite superior por um fator de cerca de $latex 4^{log(k)^2}$ até 2020. Mas, em comparação com os tamanhos dos limites do número de Ramsey, esses ajustes foram pequenos. Por outro lado, qualquer redução para o 4 na fórmula de Erdős e Szekeres R(k) < 4^k seria uma melhoria exponencial, crescendo rapidamente k fica maior.

“Parece apenas uma perguntinha bonitinha”, disse Rob Morris, um matemático do IMPA, Instituto Brasileiro de Matemática Pura e Aplicada, no Rio de Janeiro, que é coautor do novo resultado com Campos, Griffiths e Sahasrabudhe. “É um pouco sutil para apreciar. Mas as pessoas realmente se importam com isso.” Este é possivelmente um eufemismo. “Se eles tivessem provado isso em 1936, as pessoas teriam dito, OK, então qual é o problema?” disse Béla Bollobás, que foi orientadora de doutorado de Morris e Sahasrabudhe na Universidade de Memphis. “Desde então, ficou provado que é um problema muito grande, porque ao longo dos anos, vários milhares de artigos foram escritos sobre várias variantes do problema de Ramsey.” Como Liana Yepremian, um matemático da Emory University, disse: “Os números de Ramsey criam essa ponte entre combinatória, probabilidade e geometria”.

Teoria do jogo

 Em agosto de 2018, Sahasrabudhe era pós-doutorando de Morris no IMPA. Os dois esperavam iniciar um novo projeto com Griffiths, que leciona na vizinha Pontifícia Universidade Católica, quando um artigo de Conlon chamou a atenção deles. O artigo delineou uma possível estratégia para obter uma melhoria exponencial no número de Ramsey. Griffiths, Morris e Sahasrabudhe começaram a brincar com a ideia.

“Foi realmente emocionante no começo”, lembrou Sahasrabudhe. Eles levaram apenas cerca de um mês, disse ele, para fazer um esboço de seu argumento.

O plano deles era desenvolver as ideias usadas na prova original de Erdős e Szekeres de que $latex R(k) < 4^k$. Para provar que o número de Ramsey é no máximo $latex 4^k$, imagine jogar um jogo em um gráfico completo com nós $latex 4^k$. O jogo tem dois jogadores. Primeiro, seu oponente colore cada aresta de vermelho ou azul, esperando colorir as arestas de uma forma que evite a criação de um clique monocromático de k nós.

Depois que seu oponente terminar de colorir, é seu trabalho procurar um clique monocromático. Se você encontrar um, você ganha.

Para ganhar este jogo, você pode seguir uma estratégia simples. Ajuda pensar (metaforicamente) em classificar seus nós em dois baldes. Os nós em um balde formarão um clique azul e os nós no outro grupo formarão um clique vermelho. Alguns nós serão excluídos, para nunca mais serem ouvidos. No início, ambos os baldes estão vazios e cada nó é candidato a entrar em qualquer um deles.

Comece com qualquer nó que lhe agrade. Em seguida, observe as arestas de conexão. Se metade ou mais das arestas forem vermelhas, exclua todas as arestas azuis e os nós aos quais estão conectadas. Em seguida, coloque sua escolha original no balde “vermelho”. Todas as arestas vermelhas desse nó ainda estão vivas e bem, agarradas ao resto do gráfico de dentro do balde. Se mais da metade das arestas forem azuis, você exclui analogamente as arestas e os nós vermelhos e os coloca no balde azul.

Repita até que você não tenha mais nós. (Como o gráfico está completo, cada nó restante em qualquer ponto é conectado a ambos os baldes até ser colocado em um deles.)

Quando terminar, olhe dentro dos baldes. Como um nó entrou no balde vermelho somente depois que seus vizinhos azuis foram eliminados, todos os nós no balde vermelho são conectados por arestas vermelhas - eles formam um clique vermelho. Da mesma forma, o balde azul forma um clique azul. Se o seu gráfico original tiver pelo menos nós $latex 4^k$, é possível provar que um desses baldes deve conter pelo menos k nós, garantindo um clique monocromático no grafo original.

Esse argumento é inteligente e elegante, mas faz com que você construa dois cliques - um azul e um vermelho - mesmo que você realmente precise apenas de um. Seria mais eficiente ficar sempre vermelho, explicou Conlon. Nessa estratégia, você escolheria um nó a cada etapa, apagaria suas bordas azuis e o jogaria no balde vermelho. O balde vermelho se encheria rapidamente e você acumularia um grupo vermelho de k nós na metade do tempo.

Mas sua estratégia tem que funcionar para qualquer coloração vermelho-azul, e é difícil saber se você sempre encontrará um nó com muitas arestas vermelhas. Portanto, seguir a sugestão de Conlon corre o risco de encontrar um nó que quase não possui bordas vermelhas anexadas a ele. Isso forçaria você a excluir uma grande parte do gráfico de uma só vez, deixando-o lutando para construir seu clique antes de ficar sem nós. Para realizar a sugestão de Conlon, Griffiths, Morris e Sahasrabudhe precisavam provar que esse risco era evitável.

Um exame de livro aberto

Ao atualizar sua jogabilidade, Griffiths, Morris e Sahasrabudhe seguiram uma rota um pouco mais tortuosa. Em vez de construir um clique monocromático diretamente jogando os nós em seus baldes vermelhos e azuis, eles primeiro se concentraram na construção de uma estrutura chamada livro vermelho.

Um livro, na teoria dos grafos, é composto de duas partes: há um clique monocromático, chamado de “espinha”, e um segundo grupo distinto de nós chamados de “páginas”. Em um livro vermelho, todas as bordas que conectam os nós dentro da lombada são vermelhas, assim como as bordas que ligam a lombada às páginas. As bordas que conectam os nós dentro das páginas, no entanto, podem ser de qualquer combinação de cores. Conlon observou em seu artigo de 2018 que, se você encontrar um clique vermelho dentro das páginas de um livro, poderá combiná-lo com a lombada para obter um clique vermelho maior. Isso permite que você decomponha uma pesquisa por um grande clique vermelho em duas pesquisas mais fáceis. Primeiro, procure um livro vermelho. Em seguida, procure um clique nas páginas do livro.

Griffiths, Morris e Sahasrabudhe queriam ajustar o algoritmo vencedor do jogo para que ele construísse um livro vermelho em vez de um clique vermelho. Embora eles tenham estabelecido esse plano apenas algumas semanas após o início do projeto, levaria anos para fazê-lo funcionar. Eles ainda precisavam evitar a ameaça de perder todas as suas bordas vermelhas.

“Ficamos parados por muito tempo”, disse Campos, que ingressou no projeto em 2021.

Em janeiro, os quatro matemáticos concordaram em mudar para outra versão do problema. Essa versão parece mais complicada, mas acabou sendo mais fácil.

O tempo todo, a equipe se concentrou no Ramsey número R(k), também conhecido como número de Ramsey “diagonal”. Um gráfico de tamanho R(k) deve conter k nós, todos conectados por arestas da mesma cor, mas não importa se essa cor é vermelha ou azul. Por outro lado, o número de Ramsey “fora da diagonal” R(k, l) mede o tamanho que um gráfico deve ter antes de conter um clique vermelho com k nós, ou um clique azul com l nós. Em vez de continuar a resolver o problema da diagonal, o grupo decidiu tentar a versão fora da diagonal. Isso provou ser revelador.

“Por muito tempo, parecia que todas as portas que você empurrava estavam trancadas ou pelo menos muito difíceis de passar”, disse Griffiths. “E depois dessa mudança, você sentiu que todas as portas estavam abertas. De alguma forma, tudo parecia funcionar.” Na versão fora da diagonal, eles encontraram uma maneira de excluir um monte de arestas azuis de uma só vez seguindo um protocolo específico, o que aumentou a densidade das arestas vermelhas e levou a um limite aprimorado no número de Ramsey fora da diagonal. Esse método, chamado argumento de “incremento de densidade”, já havia sido usado para resolver outros problemas importantes em combinatória, mas não havia sido usado no problema do número de Ramsey.

Os quatro matemáticos então usaram o novo limite no número de Ramsey fora da diagonal para abrir caminho para o resultado da diagonal. No início de fevereiro, eles finalmente reduziram o limite do número de Ramsey por um fator exponencial, uma conquista que os matemáticos buscaram por quase um século. E eles fizeram isso modernizando a mesma linha de argumentação que Erdős e Szekeres haviam apresentado em 1935.

Épsilon, Épsilon

Após as negociações em 16 de março, os participantes começaram a confirmar os rumores. Fotos da palestra de Sahasrabudhe circularam por meio de telefonemas e mensagens privadas - mesmo em um post vago, mas sugestivo no blog do matemático Gil Kalai. Campos, Griffiths, Sahasrabudhe e Morris afirmaram ter mostrado que $latex R(k) < 3.993^k$. Naquela noite, os quatro autores postou seu papel online, permitindo que os matemáticos vejam a nova prova por si mesmos.

“Acho que muitos de nós não esperavam ver tal melhoria em nossa vida, essencialmente”, disse Matija Bucic, um matemático da Universidade de Princeton e do Instituto de Estudos Avançados. “Eu acho que é um resultado absolutamente incrível.”

Muitos especialistas estão esperançosos de que, com a queda da barreira exponencial, mais progresso se seguirá rapidamente. Os autores do novo artigo intencionalmente não levaram seu método ao limite, para evitar obscurecer seu argumento com detalhes desnecessários. “Estou muito interessado em saber até onde o método pode realmente ir, porque não tenho ideia”, disse Campos.

“É uma prova totalmente engenhosa, absolutamente maravilhosa e um avanço genuíno. Então agora espero que as comportas sejam abertas”, disse Bollobás. “Tenho convicção de que daqui a três anos o debate será sobre possíveis melhorias. Podemos melhorar de 3.993 para 3.9? Talvez para 3.4? E quanto a 3?”

A nova prova tem 56 páginas e levará semanas para que cada detalhe seja totalmente verificado pela comunidade combinatória. Mas os colegas estão otimistas. “Esse grupo de autores, são pessoas muito sérias. E são pessoas muito, muito boas em coisas muito técnicas”, disse Wigderson.

Quando se trata de seus colaboradores, Griffiths concorda. “É um privilégio trabalhar com pessoas brilhantes, não é? E acho que é por isso que me sinto muito grato”, disse ele. “Se eles tivessem deixado para mim, eu poderia ter levado mais cinco anos para acertar os detalhes.”