Humanidades

Professor de matemática faz avanços nos números de Ramsey
Quantas pessoas você precisaria em uma festa para garantir que pelo menos três pessoas se conheçam, ou que pelo menos três não se conheçam?
Por Whitney Clavin - 18/03/2021



Cortesia

Quantas pessoas você precisaria em uma festa para garantir que pelo menos três pessoas se conheçam, ou que pelo menos três não se conheçam? Pode levar algum tempo para resolver isso com papel e caneta, mas muitos matemáticos dirão prontamente que a resposta é seis. Este cenário de festa, também chamado de teorema dos "amigos e estranhos", é baseado em um conceito conhecido como números de Ramsey, em homenagem ao matemático britânico Frank Ramsey do início do século 20.

Agora, imagine que mais pessoas sejam convidadas para essa festa hipotética. Quantos seriam necessários para garantir que pelo menos cinco pessoas se conheçam, ou, inversamente, que pelo menos cinco são estranhos? A resposta não é clara. Na verdade, os matemáticos sabem apenas que o número de pessoas necessárias seria de pelo menos 43 e não mais que 48. A resposta real fica em algum lugar nesta faixa, mas é desconhecida. Adicione ainda mais pessoas à festa, e a incerteza do problema rapidamente se torna enorme.

Agora, pela primeira vez em décadas, o professor de matemática da Caltech, David Conlon, e seu colega Asaf Ferber, da UC Irvine, reduziram essa incerteza em quantidades exponenciais, para uma categoria especial de números Ramsey conhecida como números Ramsey multicoloridos. Os pesquisadores descrevem seu trabalho em um estudo publicado na revista Advances in Mathematics.

"Um dos números mais teimosos da matemática finalmente mudou", escreveu Kevin Harnett em um artigo sobre a pesquisa na revista Quanta.

“A solução surgiu muito, muito rapidamente”, diz Conlon. "Ficamos surpresos que funcionou tão bem, na verdade."

Os matemáticos pensam sobre os problemas dos números de Ramsey na forma de pontos conectados por linhas, que eles chamam de gráficos. As pessoas na festa do exemplo acima são essencialmente os pontos desses gráficos. Se os indivíduos se conhecessem, uma linha de uma cor, digamos, azul, seria desenhada entre seus respectivos pontos. Se eles não se conhecessem, seriam conectados por uma linha vermelha.

No caso descrito acima, com seis pessoas presentes na festa, pelo menos três pessoas se conhecem, ou pelo menos três pessoas não se conhecem. Assim, no gráfico que representa essa situação, haveria pelo menos um triângulo azul ou um triângulo vermelho.

“Estamos interessados ​​em saber quais padrões emergem nesses cenários”, diz Conlon. "Os números de Ramsey nos dizem que mesmo quando as coisas parecem caóticas, ainda existem padrões a serem encontrados."

No novo estudo, Conlon e Ferber analisaram os números de Ramsey onde três ou mais cores são usadas para conectar os pontos nos gráficos (daí o termo "multicolor"). Por exemplo, se você usou as cores azul, verde e vermelho para conectar os pontos, 17 pontos seriam necessários para garantir pelo menos um azul, ou um vermelho ou um triângulo verde. Pelo nosso exemplo de duas cores acima, sabemos que são necessários apenas seis pontos para garantir um triângulo vermelho ou um azul. Essencialmente, mais pontos são necessários nos cenários com várias cores.

Além disso, quando os matemáticos desejam identificar não triângulos, mas formas contendo quatro, cinco ou mais pontos, a incerteza no número total de pontos necessários aumenta ainda mais rápido para problemas multicoloridos.

Para seu trabalho, Conlon e Ferber usaram um novo tipo de prova para reduzir as incertezas multicoloridas de Ramsey em quantidades exponenciais. Eles dizem que usaram uma abordagem híbrida que combinou estratégias mais antigas, em que a aleatoriedade entra em jogo, com estratégias mais novas que são mais determinísticas.

“Descobrimos que há uma maneira melhor de resolver o problema do que colorir as conexões entre os pontos de forma aleatória”, diz Conlon. "Combinamos essa abordagem com uma em que sabemos exatamente o que estamos colorindo em uma determinada cor."

Conlon diz que agora está voltando ao problema dos números Ramsey bicolores. Para seu trabalho de doutorado em 2009, ele fez as primeiras melhorias significativas desde 1935 na redução da incerteza das soluções. Para realmente fazer melhorias dramáticas para esse tipo de problema, diz ele, algo inteiramente novo é necessário.

"O caso de duas cores provavelmente exigirá uma nova ideia tão substancial que acho que a matemática seria útil em outros problemas matemáticos não resolvidos", diz Conlon. "Em matemática, você começa porque está interessado na coisa em si mesma, mas, mais adiante, torna-se importante ou interessante por outros motivos."

O estudo, intitulado " Limites inferiores para números multicoloridos de Ramsey ", foi financiado pela National Science Foundation.

 

.
.

Leia mais a seguir