Números de Ramsey: menor do que isto, maior do que aquilo

Um dos atrativos das festas é saber quantos convidados conhecemos. Outro, talvez mais excitante, é saber quantos convidados não conhecemos. Então, a pergunta fundamental de qualquer anfitrião que se preze é a seguinte: quantos convidados são necessários para que pelo menos X deles se conheçam ou pelo menos Y deles não se conheçam? A vida do anfitrião (como a de todos nós) é bastante facilitada pela matemática.

Simplesmente porque a resposta a essa pergunta passa por uma belíssima teoria — a teoria de Ramsey —, cujas bases foram lançadas pelo matemático britânico Frank Plumpton Ramsey, em 1930. É de notar que Ramsey pensava grande, e contribuiu também com a filosofia e com a economia. Talvez um de seus principais legados tenha sido a parceria com John Maynard Keynes para (re)atrair Ludwig Wittgenstein a Cambridge.

Um dos problemas fundamentais da teoria pode ser posto assim: queremos saber quantos elementos um conjunto tem que ter para que ao menos X deles estejam conectados ou ao menos Y deles não estejam conectados. Por exemplo, se tivermos mil seguidores em uma rede social, será que dá pra garantir que ao menos 204 deles seguem-se uns aos outros? Ou que pelo menos 192 não se seguem uns aos outros?

A teoria de Ramsey garante que sim. De fato, o número de convidados que assegura que ao menos X se conheçam ou ao menos Y não se conheçam é o número de Ramsey R(X,Y). Uma curiosidade importante é que Ramsey demonstrou matematicamente que tal número existe. Mas não nos ensinou a calculá-lo. Esse número é conhecido em alguns casos particulares, eventualmente mais simples; por exemplo, se quisermos garantir que ao menos três convidados se conhecem ou ao menos três não se conhecem, estamos em busca do número de Ramsey R(3,3). Matemáticos escaldados sabem que R(3,3)=6. Ou seja, basta termos seis convidados na festa. Sabemos ainda que R(3,4)=9 e R(3,5)=14. Mas, por exemplo, não sabemos R(29,5)... E o cálculo desses números está longe de ser uma experiência trivial. Mesmo em casos tão particulares.

Conhecer o número de Ramsey não é útil apenas para quem organiza festas ou gerencia redes sociais. A teoria encontra diversas aplicações dentro da própria matemática (por exemplo, em teoria dos números) e em diversas outras disciplinas, como no desenho de canais de comunicação.

Imagine que queremos desenvolver uma rede que transmite mensagens escritas com um dado alfabeto. E sabemos que o mecanismo corre o risco de misturar algumas letras. Por exemplo, vamos supor que o mecanismo possa confundir a letra I e a letra O. Então não se distinguiria a palavra SIM da palavra SOM. O número de Ramsey nos diz qual o tamanho do alfabeto (letras convidadas pra festa) que garante que podemos escolher 23 delas que não vão ser confundidas pelo mecanismo.

Mas, de novo: salvo em alguns casos especiais, não sabemos calcular o número de Ramsey. Uma estratégia útil quando queremos conhecer uma quantidade que não sabemos calcular é procurar por limitantes. Ou seja, mesmo que não saibamos R(X,Y), gostaríamos de saber se este número está entre dois outros conhecidos. Ou seja, que tem um limitante inferior e um limitante superior. Isto nos permite sanduichar o número entre quantidades conhecidas e ter alguma ideia a respeito dele.

O problema é que estimar limitantes para o número de Ramsey ainda é uma tarefa colossal. E já atraiu profissionais brilhantes como Paul Erdös, que em 1935, num trabalho conjunto com George Szekeres, inaugurou a busca por esses limitantes. Desde então o progresso parecia estagnado.

Até outro dia. Neste ano, a teoria elevou em alguns nós a altitude de cruzeiro: descobriu-se um novo limitante superior para o número de Ramsey que melhora as estimativas anteriores. E melhora por propor técnicas novas, abordagens muito fora da caixa. Ou seja: não só traz uma resposta nova a um problema fundamental, mas também ensina novas maneiras de pensar sobre ele. E a melhor parte: é uma contribuição produzida em grande medida no Brasil, por Simon Griffiths e seus colaboradores Julian Sahasrabudhe, Marcelo Campos e Robert Morris. É matemática finíssima, descoberta entre os corredores do Departamento de Matemática da PUC-Rio, os corredores do IMPA e os da Universidade de Cambridge.

O avanço que este resultado representa para a matemática pura é fundamental. E imaginar as aplicações diversas que ele terá sobre as atividades humanas nos próximos anos (100, 200 anos…) é um exercício de diversão sem qualquer limitante superior.

*

Edgard Pimentel é pesquisador do Centro de Matemática da Universidade de Coimbra e professor da PUC-Rio.

O blog Ciência Fundamental é editado pelo Serrapilheira, um instituto privado, sem fins lucrativos, de apoio à ciência no Brasil. Inscreva-se na newsletter do Serrapilheira para acompanhar as novidades do instituto e do blog.