Pesquisadores solucionam equação que desafia matemáticos há quase um século

A descoberta foi publicada em 5 de março na revista Annals of Mathematics. Pouco progresso foi feito na resolução dos problemas de Ramsey desde a década de 1930. A solução de r(4,t) demorou quase um século para acontecer.

“Se você achar que o problema é difícil e você está preso, isso significa que é um bom problema", comenta Verstraete, em comunicado. "[A professora] Fan Chung disse que um bom problema revida. Você não pode esperar que isso simplesmente se revele”, ele disse, referindo-se à matemática autora do livro Erdös on Graphs: His Legacy of Unsolved Problems ("Erdös em Gráficos: Seu Legado de Problemas Não Resolvidos").

Na linguagem matemática, um grafo é uma série de pontos e as linhas entre esses pontos. A teoria de Ramsey sugere que se o grafo for grande o suficiente, haverá algum tipo de ordem dentro dele — seja um conjunto de pontos sem linhas entre eles ou um grupo de pontos com todas as linhas possíveis entre eles (esses conjuntos são chamados de "cliques"). Isso é representado como r(s,t) onde s são os pontos com linhas e t são os pontos sem linhas.

O problema de Ramsey mais conhecido, r(3,3), às vezes é chamado de "o teorema dos amigos e estranhos" e é explicado através de uma festa: em um grupo de seis pessoas, você encontrará pelo menos três indivíduos que se conhecem ou três que não se conhecem. A resposta para r(3,3) é seis.

"É um fato da natureza, uma verdade absoluta", explica Verstraete. "Não importa qual seja a situação ou quais seis pessoas você escolha - você encontrará três pessoas que se conhecem ou três pessoas que não se conhecem. Você pode até ser capaz de encontrar mais, mas você está garantido de que haverá pelo menos três em uma realidade ou na outra."

Os matemáticos continuaram a procurar respostas para r(4,4), r(5,5) e r(4,t). A solução para r(4,4) é 18, descoberta por um teorema criado por Paul Erdös e George Szekeres na década de 1930. O novo estudo revelou finalmente a resposta de r(4,t), mas a solução do problema r(5,5) ainda é um mistério.

Verstraete viu a equação r(4,t) pela primeira vez no livro Erdös on Graphs: His Legacy of Unsolved Problems. Em 2019, o matemático e seu colega Dhruv Mubayi, da Universidade de Illinois em Chicago, usaram grafos pseudoaleatórios para resolver r(3,t).

O que Verstraete e Mubayi descobriram foi que a amostragem desses conjuntos pseudoaleatórios frequentemente dá limites melhores nos números de Ramsey do que os grafos aleatórios. Esses limites estreitaram a faixa de estimativas que eles poderiam fazer, o que os aproximou de chegar a uma solução.

No entanto, Verstraete teve dificuldade em construir um gráfico pseudoaleatório que pudesse ajudar a resolver r(4,t). Ele começou a explorar diferentes áreas da matemática fora da combinatória, incluindo geometria finita, álgebra e probabilidade. Eventualmente, o matemático uniu forças com o pesquisador Sam Mattheus.

Após quase um ano, a dupla notou que r(4,t) está próximo de uma função cúbica de t. Ou seja: se você quer uma festa onde sempre haverá quatro pessoas que se conhecem ou t pessoas que não se conhecem, você precisará de aproximadamente t3 pessoas presentes.

"Realmente nos levou anos para resolver [esse problema]", afirmou Verstraete. "E houve muitas vezes em que ficamos presos e nos perguntamos se seríamos capazes de resolver. Mas nunca se deve desistir, não importa quanto tempo leve", ele conclui.