NOTÍCIAS

Nos últimos 88 anos, pesquisadores de todo o mundo tentaram avançar no limite superior para o Teorema de Ramsey, um dos primeiros na área de combinatória. Em janeiro deste ano, durante o Programa de Verão do IMPA, um grupo composto por Robert Morris (IMPA), Marcelo Campos (doutor pelo IMPA), Simon Griffiths (PUC-Rio) e Julian Sahasrabudhe (Cambridge) chegou a um novo algoritmo capaz de melhorar o limite do teorema. O avanço é o mais significativo na área desde 1935.

Proposto pelo britânico Frank Plumpton Ramsey (1903 –1930), o teorema procura encontrar regularidades dentro de uma estrutura larga e caótica. O estudo do problema abriu novas portas para a combinatória, ramo da matemática que estuda as maneiras pelas quais coleções finitas de objetos podem ser organizadas.

“Como esse é um dos problemas mais famosos de combinatória, quase todo mundo da área tentou resolvê-lo. E nós achávamos que seria necessária uma ferramenta muito diferente ou que precisávamos entender a ‘estrutura’ da coloração para chegar na resposta, mas a verdade é que a prova é mais simples do que todos esperavam”, disse Robert Morris.

Marcelo Campos explicou o problema usando as redes sociais como exemplo. A Teoria de Ramsey atesta que para qualquer número k, existe um número R(k) com a seguinte propriedade: se houver R(k) pessoas no Facebook, e quaisquer duas delas forem amigas ou não se conhecerem, então é possível encontrar k pessoas que são ou todas amigas umas das outras ou todas desconhecidas.

“A rede social representa o que na matemática chamamos de grafo. Para nós o que importa é a ligação entre os pontos de um grafo. Buscamos o tipo de estrutura em que todos os pontos estão interligados ou que nenhum está ligado”, explicou Campos.

Encontrar essa estrutura não é tão simples, sobretudo se a coloração – ou seja, os pares interligados – são determinados de forma “quase” aleatória.

“Esse conjunto, que no exemplo são as pessoas na rede social, pode ser pensado de várias formas. Então, pensamos que temos um ‘adversário’ que pode adotar uma estratégia que dificulte isso, para lidar com o pior cenário possível. Uma das estratégias que ele poderia adotar é conectar as pessoas aleatoriamente. Ou seja, é como se jogássemos uma moeda e ela determinasse quem é ‘amigo’ ou ‘não amigo’ dentro do Facebook. O que a gente quer provar é que o algoritmo encontra a estrutura que estamos buscando mesmo assim.”

Desafiadora, a teoria se revelou um campo vasto e foi explorada pelo matemático britânico William Timothy Gowers, ganhador da Medalha Fields, em 1998. Em uma sequência de tweets, Gowers reconheceu o progresso do grupo.

“Basicamente todos os pesquisadores de combinatória tentaram arduamente responder essa pergunta, incluindo eu mesmo”, escreveu.

Último avanço no limite superior foi em 1935

O problema é interpretado a partir da Teoria dos Grafos, onde os objetos – chamados vértices – são interligados por arestas com cores azuis ou vermelhas. Os conjuntos são chamados de “cliques” e a questão é: qual é o número de vértices necessário para garantir a existência de um clique de um certo tamanho com arestas de uma só cor?

Em 1935, Erdős e Szekeres mostraram um resultado pioneiro e chegaram ao limite superior R(k)<4^k através de um algoritmo. Campos, Griffiths, Morris e Sahasrabudhe encontraram um novo limite superior: (3,995)^k.

“É uma busca por um tipo de subestrutura em um grafo. Nós conseguimos dar a primeira melhoria exponencial para esse trabalho. Esse algoritmo permite que encontremos a subestrutura de forma mais eficiente – e funciona para qualquer grafo que você queira. Sempre vai ser possível encontrar a subestrutura”, disse Campos.

O resultado pode contribuir para a pesquisa dos especialistas em combinatória e, inclusive, gerar desdobramentos em outras áreas.

“Em um problema como esse, você quer entender o objeto, então quanto mais provas melhor. Achar provas diferentes da mesma coisa pode abrir caminhos que você nem imaginava que existiam. Esperamos que o nosso trabalho faça com que outras pessoas também encontrem provas diferentes deste teorema. A troca de ideias enriquece a matemática”, disse Morris.

Desde 2018, o grupo se reúne para explorar o problema e, após muitas tentativas, foi possível definir a melhor solução encontrada. O momento “eureca” aconteceu durante o Programa de Verão do IMPA, oportunidade única para os matemáticos se encontrarem presencialmente, visto que Julian Sahasrabudhe é professor assistente na Universidade de Cambridge.

Anteriormente, Sahasrabudhe foi pós-doutor de excelência do IMPA (2017-2018), assim como Simon Griffiths, também pós-doutor de excelência do instituto (2010-2013) e atual professor adjunto da PUC-Rio. Já Marcelo Campos foi orientado por Robert Morris no doutorado e apresentou a tese em março deste ano.

Informação disponível em https://impa.br/noticias/maior-avanco-em-88-anos-no-limite-do-teorema-de-ramsey-e-descoberto-no-impa/