Nova prova revela que os gráficos sem pentágonos são fundamentalmente diferentes

“Foi uma grande surpresa para mim que acabou sendo verdade”, disse Seymour. “Não parecia haver nenhuma razão para que fosse verdade.”

Pentear para Resultados

Para chegar ao resultado inesperado, a equipe contou com o técnica clássica de “prova por contradição”. Eles assumiram que há um contra-exemplo para a conjectura - um gráfico que não contém um cinco ciclos em lugar nenhum, mas também não tem um clique suficientemente grande ou conjunto estável, desafiando Erdős-Hajnal. “Tentamos provar tantas coisas sobre ele que não existe”, disse Seymour. E se o contra-exemplo não pudesse existir, isso significava que a conjectura devia estar certa em primeiro lugar.

O argumento real, é claro, é mais complicado. A equipe não estava interessada em qualquer contra-exemplo - eles procuraram o menor exemplo possível, que é uma tática comum na teoria dos grafos, disse Spirkl. Os matemáticos muitas vezes consideram os contra-exemplos mínimos mais fáceis de trabalhar porque podem se concentrar nas partes do gráfico que são relevantes para o problema em questão e ignorar temporariamente o resto.

“O menor contra-exemplo tem a propriedade de que, se eu excluir um único vértice, de repente ele não é mais um contra-exemplo”, disse Spirkl. O gráfico restante, que foi reduzido de n para n - 1 vértices, agora tem um clique ou conjunto estável que é tão grande que não se qualifica mais como um contra-exemplo.

A prova de cinco ciclos também construída em um pape 2020r de Pach e István Tomon que apresentou um método para encontrar certas estruturas chamadas “pentes” em um gráfico.

Para ter uma ideia de como esses pentes se parecem, imagine um gráfico que contém algo semelhante a um pente simples de dentes largos com os dentes apontando para cima. Vamos supor também que haja um vértice diretamente acima do pente, junto com as bordas que o conectam às pontas de todos os dentes. O objeto que acabamos de descrever é semelhante a um pente no sentido matemático: ali, na base de cada dente, está uma série de vértices que podem ter arestas entre eles.

Se olharmos mais de perto a aresta entre dois desses vértices, podemos seguir um caminho dessa base até os dois dentes paralelos (cada um constituindo uma aresta). A partir daí, conectamos as pontas dos dentes por meio de arestas separadas ao único vértice acima do pente, e a forma que acabamos de traçar é, na verdade, um polígono de cinco lados.

Em seu novo artigo, Chudnovsky e seus colegas refinaram o método de Pach e Tomon para mostrar que cada pequeno contra-exemplo contém, em algum lugar dentro dele, um grande pente. Isso implica que deve ter um ciclo de cinco - a única coisa que não deveria ter. E, claro, isso significa que não é um contra-exemplo de forma alguma. Ao mostrar que nenhum contra-exemplo para a conjectura foi encontrado, os quatro colaboradores provaram que a conjectura deve ser verdadeira neste caso.

Uma rota para o cume?

Agora que a pergunta dos cinco ciclos foi respondida, isso poderia levar a uma prova da conjectura completa, como Erdős e Hajnal anteciparam? “Por muito tempo, o ciclo de cinco parecia tão difícil quanto a questão geral”, disse Seymour. “A esperança era que, se pudéssemos fazer isso, poderíamos fazer a pergunta geral. Mas essa esperança diminuiu um pouco. ”

“Esta prova nem chega a nos levar até lá”, confessou Spirkl. “No momento, parece que precisaríamos de algumas novas ideias significativas.” Mas há esperança, ela acrescentou. “Pode ser o primeiro de uma longa série de etapas.”

“Resolver o caso dos cinco ciclos faz com que mais pessoas pensem que a conjectura geral deve ser verdadeira”, disse Graham. “Embora ninguém tenha encontrado uma maneira de provar isso ainda, ter um sucesso como este ajuda a espalhar a palavra.”

Mesmo por si só, a prova ainda é considerada uma grande conquista - o maior desdobramento dessa conjectura em mais de uma década, e cujos resultados não se limitam apenas ao caso dos cinco ciclos. “As técnicas que foram forçados a desenvolver para resolver este problema podem ser aplicadas a outros problemas”, disse Chvátal, “que é como fazemos progressos na matemática”.

Os quatro co-autores já começaram este processo, provando no mesmo artigo que a conjectura Erdős-Hajnal se aplica a outros casos especiais, incluindo o chamado cinco ciclos com um “chapéu” - um seis ciclos com uma borda extra que une dois vértices, formando um pentágono com um triângulo (ou chapéu) no topo.

Fonte: https://www.quantamagazine.org/new-proof-reveals-that-graphs-with-no-pentagons-are-fundamentally-different-20210426/