David Conlon e Asaf Ferber aumentaram o limite inferior para os “números de Ramsey” multicoloridos, que quantificam o quão grandes os gráficos podem ficar antes que os padrões inevitavelmente surjam.
Depois de mais de 70 anos de intransigência, um dos números mais teimosos da matemática finalmente mudou.
Em uma prova de quatro páginas postada no final de setembro, David Conlon e Asaf Ferber forneceram a estimativa mais precisa até então para “números de Ramsey multicoloridos”, que medem quão grandes os gráficos podem se tornar antes de inevitavelmente exibirem certos tipos de padrões.
“Não há aleatoriedade absoluta neste universo”, disse Maria Axenovich do Instituto de Tecnologia de Karlsruhe, na Alemanha. “Sempre há grupos de ordem, e os números de Ramsey quantificam isso.”
Os gráficos são coleções de pontos (vértices) conectados por linhas (arestas). Os matemáticos estão particularmente interessados em entender quantos vértices e arestas eles podem conter antes que diferentes tipos de subestruturas surjam dentro deles.
“Se você tem um gráfico grande o suficiente, uma grande parte dele é bem ordenada”, disse Maria Chudnovsky, da Universidade de Princeton. “É difícil explicar por que algo é bonito, mas há um consenso universal de que este é um fenômeno bonito.”
Os números de Ramsey referem-se a um padrão particular denominado clique monocromático, que é um conjunto de vértices que são todos conectados uns aos outros por arestas da mesma cor depois de executar um procedimento de coloração específico.
Os números de Ramsey variam de acordo com o tamanho do clique que você está procurando e o número de cores que você usa para fazer a coloração. Os matemáticos não podem calcular a maioria dos números de Ramsey porque todos, exceto os menores gráficos, são muito complexos para serem analisados diretamente.
Normalmente, o melhor que os matemáticos podem fazer é definir uma gama de valores possíveis para os números de Ramsey. É como se você quisesse saber a localização de um amigo, mas só pudesse determinar com certeza que ele está ao norte de Miami e ao sul da Filadélfia.
A nova prova faz mais para zerar o valor exato dos números de Ramsey do que qualquer resultado desde que Paul Erdős os estudou pela primeira vez nas décadas de 1930 e 1940. Conlon, do California Institute of Technology, e Ferber, da University of California, Irvine, encontraram um novo “limite inferior” para números Ramsey multicoloridos que é exponencialmente mais preciso do que a melhor estimativa anterior. Seu resultado fornece aos matemáticos uma nova compreensão da interação entre ordem e aleatoriedade nos gráficos, que são de interesse fundamental na matemática.
“Este é um resultado fantástico”, disse Axenovich. “Eu amo isso.”
Conexões Coloridas
Os números de Ramsey, introduzidos pelo polímata britânico Frank Ramsey na década de 1920, são mais bem compreendidos por meio de exemplos. Comece com um gráfico com cinco vértices. Conecte cada um deles a todos os outros para formar o que os matemáticos chamam de gráfico completo. Agora, você pode colorir cada aresta de vermelho ou azul sem criar um conjunto de três vértices que estão todos conectados entre si por arestas da mesma cor? A resposta é: você pode.
Mas comece com um gráfico completo de seis vértices, e agora não há como colorir as bordas com duas cores sem criar um clique monocromático de pelo menos três vértices. Ou, dito de outra forma, para duas cores e um clique de tamanho 3, o número de Ramsey é 6 (já que requer um grafo completo de seis vértices).
Os números de Ramsey variam dependendo do número de cores e do tamanho do clique monocromático que você está procurando. Mas, em geral, eles são difíceis de calcular com exatidão, e os matemáticos só sabem valores exatos para um pequeno número de situações. Mesmo para cliques pequenos de tamanho 5 (e duas cores), o melhor que eles podem dizer é que o número de Ramsey está entre 43 e 48.
“É realmente constrangedor”, disse Yuval Wigderson, um estudante de graduação da Universidade de Stanford. “Estamos trabalhando nesse problema há quase 100 anos e não sabemos de nada.”
Os números de Ramsey são difíceis de calcular porque a complexidade de um gráfico aumenta drasticamente à medida que você adiciona vértices. Para um gráfico com seis vértices e duas cores, você pode percorrer todas as possibilidades manualmente. Mas para um gráfico com 40 vértices, existem 2780 maneiras de aplicar duas cores.
“Há muito para verificar”, disse Axenovich.
Entre os matemáticos que estudam os números de Ramsey, há uma parábola, geralmente atribuída a Erdős, que captura a rapidez com que esses cálculos se tornam proibitivos. Um dia, alienígenas hostis invadem. Eles se oferecem para poupar o planeta se pudermos produzir os números corretos de Ramsey. De acordo com a parábola, se eles pedem o número de Ramsey para cliques de duas cores de tamanho 5, devemos usar todos os recursos da civilização humana para encontrá-lo. Mas se eles pedirem um clique de tamanho 6, devemos nos preparar para a batalha.
“Se eles nos pedirem o número de Ramsey 6, esqueça, nós lançamos um ataque”, disse Axenovich.
Explorando a aleatoriedade
Como calcular os números exatos de Ramsey é em grande parte impossível, os matemáticos em vez disso se concentram neles, provando que são maiores do que algum “limite inferior” e menores do que algum “limite superior”. O novo trabalho melhora a precisão dos limites inferiores, mas não aborda os limites superiores.
Em 1935, Erdős e George Szekeres estabeleceram o primeiro limite desse tipo. Eles usaram uma pequena prova para mostrar que os números de Ramsey de duas cores devem ser menores do que um limite superior de 4t, onde t é o tamanho do clique monocromático em que você está interessado. Eles também descobriram que os números de Ramsey de três cores devem ser menores do que 27t. Uma década depois, em 1947, Erdős calculou os primeiros limites inferiores para esses números: para duas cores é (√2)t vértices e para três cores é (√3)t.
Há uma grande diferença entre (√2)t e 4t, especialmente quando t fica muito grande. Essa lacuna reflete o entendimento impreciso dos matemáticos sobre os números de Ramsey. Mas a forma dos limites – a maneira como o tamanho do grafo necessário é expresso em termos do tamanho do clique desejado – indica o que os matemáticos mais querem saber.
“O que realmente gostaríamos de entender é o comportamento de crescimento desses números [de Ramsey] conforme o tamanho da camarilha aumenta”, disse Lisa Sauermann, pós-doutoranda no Institute for Advanced Study em Princeton, New Jersey.
Por esse motivo, a contribuição mais duradoura de Erdős para o estudo dos números de Ramsey não foram os limites em si – foi o método que ele usou para calculá-los. Aqui está o que ele fez para o limite inferior.
Imagine que você tem um gráfico completo com 10 vértices e 45 arestas. E imagine que você queira saber se é possível aplicar três cores sem criar um clique monocromático de algum tamanho específico, digamos cinco vértices (conectados por 10 arestas).
Você pode começar, como Erdős fez, colorindo as bordas aleatoriamente. Para cada aresta, role o equivalente a um dado de três lados e aplique a cor que aparecer. Erdős sabia que a probabilidade de qualquer subconjunto particular de 10 arestas acabar com a mesma cor é fácil de calcular. É apenas a probabilidade de que uma aresta seja, digamos, vermelha, vezes a probabilidade de que outra aresta seja vermelha, e assim por diante para todas as 10 arestas (então 1/310). Em seguida, ele multiplicou esse valor por 3 para explicar o fato de que existem três cores diferentes que poderiam produzir a clique monocromática desejada.
Erdős então olhou para o número total de cliques diferentes de cinco vértices no gráfico. Existem 252 deles. Finalmente, ele pegou a probabilidade de que um deles produziria um clique monocromático e acrescentou às probabilidades de que qualquer um dos outros 251 produziria o clique. Este é um cálculo conhecido como “limite de união” e estima a probabilidade de produzir um clique monocromático ao colorir as bordas aleatoriamente.
Contanto que o limite da união permaneça abaixo de 1, você sabe que o método de coloração aleatória não tem garantia de produzir o clique monocromático fornecido. Em nosso exemplo, o limite da união é 0,0128. Isso significa que você está longe de ter garantido um clique monocromático de 5 vértices, o que significa que o número de Ramsey para este exemplo é maior do que 10 vértices.
Os matemáticos chamam essa abordagem de método probabilístico. É uma solução engenhosa para um problema que de outra forma seria intratável. Em vez de ter que encontrar exemplos de colorações que não contêm cliques monocromáticos de tamanhos diferentes, Erdős simplesmente provou que essas colorações sem clique devem existir (porque o limite de união é menor que 1) – o que significa que o número de Ramsey deve ser maior que o número de vértices no gráfico que você está colorindo aleatoriamente.
“Somos capazes de provar que algo existe sem realmente mostrar o que é”, disse Wigderson.
Nos 70 anos seguintes, os matemáticos melhoraram o limite inferior de Erdős para duas e três cores apenas uma vez – em 1975, com um aperto incremental por Joel Spencer. Muitas pessoas trabalharam no problema, mas nenhuma conseguiu encontrar uma maneira melhor do que o método probabilístico de calcular os números de Ramsey. “O problema tem sido tentar derrotar esse [limite] vindo da amostragem aleatória”, disse Conlon.
E foi isso que Conlon e Ferber finalmente fizeram neste outono.
Ordem de Incorporação
A nova prova melhora o limite inferior dos números de Ramsey para três ou mais cores.
Antes do trabalho de Conlon e Ferber, o limite inferior para três cores era (√3)t (aproximadamente 1,73)t. Eles melhoraram esse limite para 1.834t. Para quatro cores, eles aumentaram o limite inferior de 2t para 2,135t. Ambos são saltos gigantescos. Ao aumentar o número de base elevado à potência t, Conlon e Ferber provaram que existem gráficos exponencialmente maiores de três e quatro cores que não possuem os cliques monocromáticos necessários. Em outras palavras, eles mostraram que a desordem pode persistir em gráficos maiores do que os conhecidos anteriormente.
O objetivo de Conlon e Ferber era colorir um gráfico completo sem criar grandes cliques monocromáticos. Para fazer isso, eles descobriram uma maneira de distribuir com eficiência uma cor (vermelho) de acordo com uma regra fixa antes de aplicar as cores restantes ao acaso. Este método híbrido proporcionou a eles controle adicional sobre a estrutura do gráfico que Erdős não tinha.
Para a parte fixa do plano, eles colocaram os vértices em um tipo especial de espaço geométrico, de forma que cada vértice fosse definido por um conjunto de coordenadas. Em seguida, eles decidiram quais bordas colorir de vermelho por meio de um processo de duas etapas.
Primeiro, eles pegaram as coordenadas de cada vértice, as elevaram ao quadrado e as adicionaram – um processo conhecido como soma dos quadrados. Devido à natureza deste espaço geométrico particular, esta operação de soma de quadrados produziu um de dois valores: 0 ou 1. Em seguida, focando apenas nos vértices cuja soma de quadrados era 0, eles calcularam o “produto interno” entre os pares de vértices – uma operação padrão em álgebra linear. Se uma aresta conectava um par cujo produto interno era um certo valor, eles o coloriam de vermelho. Isso foi responsável por metade das arestas totais.
Depois de concluir essa parte determinística de sua abordagem, Conlon e Ferber passaram para a parte aleatória. Para as arestas restantes, eles jogaram uma moeda – exatamente como Erdős faria – para determinar se uma determinada aresta era colorida de azul ou verde.
Essa abordagem acabou sendo uma ótima maneira de evitar a formação de cliques monocromáticos conforme o tamanho de um gráfico aumenta. Isso foi intencional: a dupla projetou a etapa determinística para gerar bordas vermelhas que foram espalhadas por todo o gráfico. À distância, eles pareceriam quase como se tivessem sido espalhados ao acaso – e de fato, Conlon e Ferber se referem a esse arranjo de bordas vermelhas como “pseudoaleatório”.
Essa distribuição pseudo-aleatória de bordas vermelhas atinge duas coisas desejáveis. Em primeiro lugar, ao espalhar as bordas vermelhas, isso garante que você não acabe com qualquer cliques vermelhos grandes (que é o que você está tentando evitar se quiser aumentar o limite inferior). Em segundo lugar, as bordas vermelhas espalhadas quebram o gráfico, deixando menos espaços abertos que podem acabar sendo preenchidos aleatoriamente por cliques monocromáticos de outra cor.
“Queríamos ter certeza de que a primeira cor, que usamos de forma determinística, reduziu o número de cliques potenciais”, disse Ferber.
Os matemáticos reagiram à nova prova rapidamente. Poucos dias depois de seu lançamento, Wigderson postou um artigo de acompanhamento que usava seus métodos para provar um limite inferior ainda um pouco melhor para os números de Ramsey para quatro ou mais cores. Após décadas de estagnação nos números de Ramsey, a barragem finalmente se rompeu.
“Nosso estado de conhecimento está paralisado desde Erdős nos anos 40, então qualquer coisa que forneça uma nova abordagem para questões desse tipo é empolgante”, disse Wigderson.
Publicado em 06/11/2020 21h04
Artigo original:
Estudo original:
Achou importante? Compartilhe!
Assine nossa newsletter e fique informado sobre Astrofísica, Biofísica, Geofísica e outras áreas. Preencha seu e-mail no espaço abaixo e clique em “OK”: