Grupo carioca avança em problema que desafia matemáticos há mais de 90 anos

• História exposta: Professor cataloga azulejos raros que encontra nos botecos espalhados pelo Rio
• Achados! Repórter narra aventuras em sebos do Rio e abre acervo particular, com relíquias

O pesquisador Marcelo Campos e seu orientador de doutorado Robert Morris aprimoraram a solução de um problema na estrutura abstrata de “grafos” (conjuntos de pontos interligados), que tem aplicação potencial em estudos de epidemiologia, computação, finanças e outras áreas.

O enigma atacado pelos pesquisadores, chamado teorema de Ramsey, envolve a busca de fórmulas para entender o comportamento dessas estruturas. Grafos estão na base matemática de aplicativos como o Waze e outros que usam análise combinatória para achar caminhos no trânsito, e são um campo vasto de problemas em aberto.

A charada atacada pelo grupo carioca, criada pelo matemático Frank Ramsey em 1930, pode ser exemplificada como uma questão de conexões entre pessoas:

Qual tamanho mínimo um grupo de pessoas precisa ter para que, num subgrupo, todos se conheçam (formem uma “panelinha”) ou nenhum deles se conheça (uma “antipanelinha”)?

A resposta é conhecida para casos simples (subgrupos de até quatro pessoas), mas para cinco nenhum matemático solucionou o problema ainda. (Veja abaixo)

• Novo point: Beco da Cirrose passa por remodelação e vira novo polo gastronômico e de boemia da Zona Norte

Em 1935, o matemático húngaro Paul Erdos formulou junto com seu colega George Szekeres uma prova de que existe um limite máximo para encontrar uma panelinha de um determinado tamanho k, que é o de 4k (4 elevado a k). Esse limite, porém, é uma regra geral pouco precisa. Já se sabe que, para casos menores, a solução real está muito abaixo do limite 4k.

Desde a década de 1930, de qualquer modo, nenhum matemático tinha conseguido uma regra geral melhor para estabelecer esse limite. Até que o trabalho feito no Rio por Campos e Morris, que teve como coautores Simon Griffiths, da PUC-Rio, e Julian Sahasrabudhe, da Universidade de Cambridge (Inglaterra), apresentou finalmente um avanço.

Num estudo matemático que ocupa 56 páginas de cálculos e demonstrações, os cientistas oferecem uma fórmula que reduz um pouco o limite máximo para o número k no teorema de Ramsey — no exemplo acima, em vez de 4k a solução ficaria como 3,9995k).

• Mais verde: Voluntários atuam em reflorestamento da Pedra do Arpoador

1 - O teorema de Ramsey pode ser exemplificado num diagrama como uma trama de pessoas que se conhecem ou que não se conhecem. Pontos representam pessoas, e cores das arestas sua relação.

2 - Em um grupo com certo número de pessoas, sempre vai haver um subgrupo mínimo de pessoas na qual todas se conhecem (uma “panelinha”) ou em que nenhuma se conhece (uma “antipanelinha”).

3 - No diagrama de um grupo de 6 pessoas, matemáticos sabem que sempre vai haver um subgrupo de ao menos 3 delas (um triângulo) que se conhecem ou são todas estranhas entre si.

4 - Para garantir que vamos encontrar uma “panelinha” de 4 amigos (ou uma “antipanelinha”), o número total do grupo tem que aumentar para 18 indivíduos.

5 - Para achar um subgrupo de 5 pessoas todas ligadas pela mesma cor, porém, matemáticos não sabem ainda o tamanho do número que o grupo precisa ter. O desafio permanece aberto.

Avanços - Não se conhece uma fórmula capaz de calcular valores para o Teorema de Ramsey. Mas matemáticos do IMPA, no Rio, conseguiram determinar um "teto" para os valores, o maior avanço no campo desde 1935.

Aplicações - O teorema é um campo de pesquisa abstrato, mas com potencial de aplicação em diferentes áreas como epidemiologia, finanças e, claro, o estudo de redes sociais.

A pequena redução no número pode não parecer significativa, mas foi celebrada como grande avanço por matemáticos mundo afora. Um deles foi Timothy Gowers, colega de Sahasrabudhe em Cambridge, que viu o jovem demonstrar o teorema num seminário.

• Violência 2.0: Milicianos e traficantes praticam extorsão via Pix

Gowers é ganhador da Medalha Fields, láurea equivalente ao prêmio Nobel da matemática, e descreveu o trabalho de Campos, Morris, Griffiths e Sahasrabudhe como “sensacional” no Twitter.

“Todos os especialistas em combinatória trabalharam duro para resolver essa questão — incluindo eu mesmo — e é seguro dizer que esse está entre os dois ou três problemas mais proeminentes em combinatória extremal. Talvez seja o mais proeminente”, disse o pesquisador.

Muitos trabalhos que tentaram resolver o problema de Ramsey empregavam aleatoriedade, pela geração randômica de redes de conexão para investigar seu comportamento, e o conceito correlato de pseudoaleatoriedade. Apesar de ter gerado ideias interessantes, até mesmo aplicadas em ciência da computação, a técnica não levou a avanço no teorema em si.

Em seu trabalho, Morris e Campos lançam mão do conceito de aleatoriedade para alguns fins, mas seguiram um caminho diferente para construir seu algoritmo, o conjunto de regras que permite atacar o problema.

• Estratégia: Escola pública adapta sistema de cultivo para produzir os próprios alimentos e tem iniciativa premiada

A ideia dos pesquisadores foi imaginar um cenário em que seu acesso à informação sobre as redes era limitado, porque alguém as teria apagado, e o algoritmo então precisaria superar isso.

— É como se a gente tivesse um adversário querendo impedir a gente de achar essas subestruturas, mas a gente inventa um jeito de burlar esse adversário, com uma nova técnica — disse Campos em entrevista ao GLOBO.

A solução criada pelos pesquisadores foi revelada publicamente quando estes apresentaram seminários todos no mesmo dia, cada um em uma instituição em 16 de março.

Para Gowers, a técnica usada pelo quarteto de matemáticos para chegar a uma resposta foi completamente inusitada. Ele conta que se surpreendeu no seminário de Sahasrabudhe.

“Entrei lá achando que eu iria ficar com aquela sensação de que eu poderia ter conseguido solucionar o problema sozinho caso eu tivesse pensado um pouquinho mais” escreveu o pesquisador no Twitter. “Mas eu não tive essa sensação. A prova era muito diferente do tipo de argumento que eu tinha buscado, e não acho que jamais teria sido capaz de achá-la.”

• Coleta de tampinhas, hortas e limpeza de praias: escolas apostam em ensino sobre sustentabilidade

A receita que envolveu a descoberta teve um brasileiro (Campos), dois britânicos (Morris e Griffiths) e um canadense (Sahasrabudhe). Mas o cenário de trabalho que os uniu foi o Rio. Todos passaram em algum momento (ou passam) pelo Impa como pesquisadores e formam um grupo carioca na essência.

A ideia para o novo estudo, que saiu de um encontro de verão no instituto à beira da Floresta da Tijuca, envolveu por parte dos matemáticos dar um passo atrás em ideias anteriores e simplificar suas abordagens, conta Morris.

— Quando deu certo, foi algo surpreendente até mesmo para a gente — diz. — A gente estava tentando fazer uma coisa bem mais complicada e, seguindo esse caminho, não estávamos conseguindo. Só depois a gente achou essa solução, que realmente é bem mais simples do que o que a gente estava esperando.

• Imunização: Rio aplica mais de 200 mil doses em 'Dia D' de vacinação contra a gripe

Os matemáticos submeteram a primeira versão do trabalho para o portal Arxiv.org, onde o estudo fica aberto ao escrutínio de todos os pesquisadores da área. A divulgação imediata de propostas de solução é praxe na matemática, e o artigo ainda está passando por revisão independente em uma revista especializada. Até agora, porém, não houve contestações à solução dos pesquisadores.

E, apesar de o grupo ter conseguido vencer um problema de quase um século de idade, Morris afirma que a solução em si não deve ter aplicações ainda, algo esperado em matemática pura.