Todos nós já passamos por isso: encarar uma prova de matemática com um problema que parece impossível de resolver. E se encontrar a solução para um problema demorasse quase um século? Para os matemáticos que se interessam pela teoria de Ramsey, esse é o caso. Na verdade, pouco progresso foi feito na resolução dos problemas de Ramsey desde a década de 1930.
Leia também Paleontólogos desenterram lampreias jurássicas gigantes
Agora, os pesquisadores da Universidade da Califórnia em San Diego, Jacques Verstraete e Sam Mattheus, encontraram a resposta para r(4,t), um antigo problema de Ramsey que deixou perplexo o mundo da matemática por décadas.
Qual era o problema de Ramsey, afinal?
Na linguagem matemática, um gráfico é uma série de pontos e as linhas entre esses pontos. A teoria de Ramsey sugere que se o gráfico for grande o suficiente, é garantido que você encontrará algum tipo de ordem dentro dele – seja um conjunto de pontos sem linhas entre eles ou um conjunto de pontos com todas as linhas possíveis entre eles (esses conjuntos são chamados “panelinhas”). Isso é escrito como r(s,t) onde s são os pontos com linhas e t são os pontos sem linhas.
Para aqueles de nós que não lidam com teoria dos grafos, o problema de Ramsey mais conhecido, r(3,3), às vezes é chamado de “o teorema sobre amigos e estranhos” e é explicado por meio de uma festa: em um grupo de seis pessoas, você encontrará pelo menos três pessoas que se conhecem ou três pessoas que não se conhecem. A resposta para r(3,3) é seis.
“É um fato da natureza, uma verdade absoluta”, afirma 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 conseguir encontrar mais, mas você é garantido que haverá pelo menos três em um grupo ou outro.”
O que aconteceu depois que os matemáticos descobriram que r(3,3) = 6? Naturalmente, eles queriam saber r(4,4), r(5,5) e r(4,t) onde o número de pontos que não estão conectados é variável. A solução para r(4,4) é 18 e é provada usando um teorema criado por Paul Erdös e George Szekeres na década de 1930.
Atualmente r(5,5) ainda é desconhecido.
Um bom problema contra-ataca
Por que algo tão simples de ser declarado é tão difícil de resolver? Acontece que é mais complicado do que parece. Digamos que você soubesse que a solução para r(5,5) estava em algum lugar entre 40–50. Se você começasse com 45 pontos, haveria mais de 10.234 gráficos a serem considerados.
“Como esses números são notoriamente difíceis de encontrar, os matemáticos procuram estimativas”, explicou Verstraete. “Isso é o que Sam e eu alcançamos em nosso trabalho recente. Como encontramos não a resposta exata, mas as melhores estimativas para quais poderiam ser esses números de Ramsey?”
Os estudantes de matemática aprendem sobre os problemas de Ramsey desde cedo, então r(4,t) esteve no radar de Verstraete durante a maior parte de sua carreira profissional. Na verdade, ele viu o problema impresso pela primeira vez em Erdös on Graphs: His Legacy of Unsolved Problems, escrito por dois professores da UC San Diego, Fan Chung e o falecido Ron Graham. O problema é uma conjectura de Erdös, que ofereceu US$ 250 à primeira pessoa que conseguisse resolvê-lo.
“Muitas pessoas pensaram em r(4,t) – é um problema aberto há mais de 90 anos”, disse Verstraete. “Mas não era algo que estava na vanguarda da minha pesquisa. Todo mundo sabe que é difícil e todos tentaram descobrir, então, a menos que você tenha uma ideia nova, provavelmente não chegará a lugar nenhum.”
Então, há cerca de quatro anos, Verstraete estava trabalhando em um problema de Ramsey diferente com um matemático da Universidade de Illinois-Chicago, Dhruv Mubayi. Juntos, eles descobriram que os gráficos pseudoaleatórios poderiam avançar o conhecimento atual sobre esses problemas antigos.
Em 1937, Erdös descobriu que o uso de gráficos aleatórios poderia fornecer bons limites inferiores para problemas de Ramsey. O que Verstraete e Mubayi descobriram foi que a amostragem de gráficos pseudoaleatórios frequentemente fornece limites melhores para números de Ramsey do que gráficos aleatórios. Estes limites – limites superiores e inferiores para a resposta possível – estreitaram o leque de estimativas que podiam fazer. Em outras palavras, eles estavam se aproximando da verdade.
Em 2019, para deleite do mundo da matemática, Verstraete e Mubayi usaram gráficos pseudoaleatórios para resolver r(3,t). No entanto, Verstraete lutou para 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, ele juntou forças com Mattheus, um pós-doutorado em seu grupo cuja formação era em geometria finita.
“Descobriu-se que o gráfico pseudoaleatório de que precisávamos poderia ser encontrado em geometria finita”, afirmou Verstraete. “Sam era a pessoa perfeita para vir e ajudar a construir o que precisávamos.”
Depois de colocar o gráfico pseudoaleatório no lugar, eles ainda tiveram que decifrar várias peças matemáticas. Demorou quase um ano, mas finalmente eles perceberam que tinham uma solução: r(4,t) está próximo de uma função cúbica de t. Se você quiser uma festa onde sempre haverá quatro pessoas que se conhecem ou pessoas que não se conhecem, você precisará de aproximadamente três pessoas presentes. Há um pequeno asterisco (na verdade, um o) porque, lembre-se, esta é uma estimativa, não uma resposta exata. Mas t3 está muito próximo da resposta exata.
As descobertas estão atualmente sob revisão nos Annals of Mathematics. Um resumo pode ser visualizado no arXiv.
“Realmente levamos anos para resolver”, afirmou Verstraete. “E houve muitas vezes em que ficamos presos e nos perguntamos se seríamos capazes de resolver isso. Mas nunca se deve desistir, não importa quanto tempo leve.”
Verstraete enfatiza a importância da perseverança – algo que ele lembra frequentemente aos seus alunos. “Se você achar que o problema é difícil e você está preso, isso significa que é um bom problema. Fan Chung disse que um bom problema revida. Você não pode esperar que ele simplesmente se revele.”
Verstraete sabe que essa determinação obstinada é bem recompensada: “Recebi uma ligação de Fan dizendo que ela me deve US$ 250.”
Traduzido por Mateus Lynniker de Phys.Org
