Graph Puzzles II.1: Counterexamples to Jain's Second Unit Vector Flows Conjecture

Este artigo apresenta dois contraexemplos à segunda conjectura de Jain sobre fluxos de vetores unitários, demonstrando que certos conjuntos de pontos na esfera exigem valores fora do intervalo previsto, o que invalida a implicação conjunta das conjecturas de Jain para a conjectura do fluxo 5 de Tutte.

O essencial

Imagine que você tem um mapa do mundo (uma esfera) e precisa desenhar setas em todas as estradas de uma cidade complexa. O objetivo é garantir que, em cada cruzamento, o "tráfego" que entra seja exatamente igual ao "tráfego" que sai. Isso é o que os matemáticos chamam de fluxo.

Agora, vamos complicar um pouco: em vez de usar números simples (como 1, 2 ou 3) para medir o tráfego, vamos usar setas tridimensionais que têm o mesmo tamanho (como setas de um compasso perfeito).

O matemático K. Jain fez uma aposta ousada (uma conjectura) sobre isso. Ele disse:

1. Para qualquer cidade sem "estradas mortas" (pontes), é possível fazer esse fluxo com setas perfeitas.
2. Existe uma "tabela de regras" mágica que converte qualquer ponto na esfera em um número pequeno (de -4 a 4), de forma que, se você pegar três pontos que formam um triângulo perfeito na esfera, a soma dos seus números seja zero.

Se as duas apostas de Jain estivessem corretas, elas provariam uma das maiores lendas da matemática: a Conjectura do Fluxo 5 de Tutte, que diz que todo mapa de estradas pode ser colorido ou organizado usando apenas 5 cores (ou valores) sem conflitos.

O que este paper descobriu?

O autor, Nikolay Ulyanov, disse: "Espera aí, a segunda aposta de Jain está errada".

Ele construiu dois "quebra-cabeças" (conjuntos de pontos na esfera) que funcionam como armadilhas. Imagine que você tenta pintar esses pontos usando apenas as cores de uma caixa de lápis de cor com 8 cores (de -4 a 4).

• A Armadilha: Ulyanov mostrou que, para esses dois desenhos específicos, é impossível pintar tudo usando apenas essas 8 cores seguindo as regras de Jain.
• O Problema: Para resolver o quebra-cabeça, você é forçado a pegar um lápis de cor extra, que não estava na caixa original. Você precisa de valores como -5 e 5.

Isso significa que a "tabela mágica" de Jain não existe da maneira que ele imaginou. Você não consegue encaixar todos os pontos da esfera nesses valores pequenos sem quebrar as regras.

Como ele fez isso? (As Analogias)

O autor usou duas abordagens criativas para criar essas armadilhas:

1. A Expansão do Icosidodecaedro (O "Poliedro Esticado"):
   Ele pegou uma forma geométrica famosa (o Icosidodecaedro, que parece uma bola feita de triângulos e pentágonos) e "esticou" cada ponto dela. Imagine que cada ponto virou um pequeno anel. Onde esses anéis se cruzam, surgiram novos pontos. O resultado foi um conjunto de 50 pontos que, quando você tenta aplicar as regras de Jain, explode em uma contradição. É como tentar encaixar um cubo grande em uma caixa pequena: não cabe!

2. A Construção de Raiz Quadrada (O "Algoritmo Matemático"):
   Na segunda tentativa, ele usou uma receita matemática mais complexa, misturando raízes quadradas e permutações de números, para criar um conjunto menor de 36 pontos. Mesmo sendo menor, esse grupo também se recusou a obedecer às regras de Jain, exigindo novamente o uso do "lápis proibido" (o valor 5).

Por que isso importa?

É como se você estivesse tentando provar que um jogo de tabuleiro é impossível de ganhar com apenas 5 peças. Jain disse: "Não, é possível, basta usar essa regra mágica de conversão".

Ulyanov pegou o tabuleiro, montou um cenário específico e mostrou: "Veja, com essa regra mágica, você fica preso. Precisa de uma sexta peça".

O que isso significa para o futuro?

• A Conjectura de Jain (a segunda) foi derrubada.
• A grande Conjectura de Tutte (sobre o fluxo 5) ainda está em jogo! O autor sugere que talvez a "tabela mágica" precise ser diferente, talvez usando pontos infinitos ou com propriedades especiais, para que a prova de Tutte ainda funcione.
• O autor já está trabalhando na próxima parte da série para tentar salvar a ideia de Tutte, mas com novas regras.

Resumo em uma frase: O autor provou que a "receita mágica" de Jain para converter pontos da esfera em números pequenos não funciona para todos os casos, forçando os matemáticos a repensarem como provar uma das maiores teorias sobre mapas e cores.

Resumo técnico

Resumo Técnico: Contraexemplos à Segunda Conjectura de Jain sobre Fluxos de Vetores Unitários

1. O Problema e o Contexto

O artigo aborda problemas fundamentais na teoria dos fluxos em grafos e geometria combinatória, especificamente relacionados às conjecturas propostas por K. Jain sobre fluxos de vetores unitários em 3 dimensões.

• Conceito Central: Um fluxo de vetor unitário em um grafo $G$ atribui a cada aresta um vetor tridimensional de norma unitária (pertencente à esfera $S^2$).
• Conjectura 1.1 (Fluxos de Vetores Unitários): Todo grafo sem pontes (bridgeless) possui tal fluxo.
• Conjectura 1.2 (Fluxo $S^2$ não nulo de valor 5 - $nz5$): Existe uma aplicação $q: S^2 \to \{-4, -3, -2, -1, 1, 2, 3, 4\}$ tal que:
  1. Pontos antipodais recebem valores opostos ($q(-x) = -q(x)$).
  2. A soma dos valores de quaisquer três pontos equidistantes em um grande círculo é zero.
• Implicação Teórica: Se ambas as conjecturas de Jain fossem verdadeiras, elas implicariam a famosa Conjectura do Fluxo 5 de Tutte, que afirma que todo grafo cúbico sem pontes possui um fluxo não nulo de valor 5.

O objetivo do artigo é refutar a Conjectura 1.2, demonstrando que existem subconjuntos finitos de pontos na esfera $S^2$ que exigem valores fora do conjunto $\{-4, \dots, 4\}$ (especificamente, exigem valores $\pm 5$), tornando impossível um fluxo $nz5$ para esses conjuntos.

2. Metodologia

O autor utiliza uma abordagem combinatória e computacional rigorosa para construir e verificar os contraexemplos:

• Construção Geométrica:
  • Identificação de configurações de pontos na esfera baseadas em sólidos platônicos e arquimedianos (como o Icosidodecaedro).
  • Criação de novos conjuntos de pontos através de expansões geométricas (interseção de pequenos círculos equidistantes) e geração de coordenadas baseadas em aritmética de raízes quadradas.
• Formulação como Problema SAT (Satisfatibilidade Booleana):
  • O problema de atribuir valores aos pontos, respeitando as restrições de antipodalidade e soma nula em triplas de grandes círculos, é codificado como uma instância de Satisfatibilidade Booleana (CNF).
  • Para cada ponto antipodal, são introduzidas variáveis booleanas representando os valores permitidos $\{-4, \dots, 4\}$.
  • São impostas restrições de "exatamente um" (um valor por ponto), restrições antipodais e restrições de soma das triplas.
• Verificação Computacional:
  • Uso de solucionadores SAT (PicoSAT/pycosat) para provar a insatisfatibilidade das fórmulas CNF geradas.
  • Validação adicional utilizando o assistente de prova Lean 4 (com a tática bv_decide) para garantir a correção formal dos resultados.
  • Uso de aritmética exata e tolerância numérica ($\epsilon = 10^{-7}$) para detecção precisa de triplas em grandes círculos.

3. Principais Contribuições e Resultados

O artigo apresenta dois contraexemplos concretos que refutam a Conjectura 1.2:

Contraexemplo 1: Expansão de 50 pontos do Icosidodecaedro

• Construção: Parte-se do conjunto de 30 pontos do Icosidodecaedro. Para cada ponto, define-se um pequeno círculo. Interseções de círculos correspondentes a pares de pontos com distância esférica $2\pi/5$ geram novos pontos.
• Resultado: O conjunto final possui 50 pontos e 40 triplas em grandes círculos.
• Estrutura Gráfica: Ao considerar pontos antipodais como equivalentes, o conjunto revela uma estrutura que combina o Grafo de Petersen e um Escadão de Möbius (Möbius ladder) de 10 vértices.
• Verificação: A fórmula CNF (200 variáveis, 19.765 cláusulas) foi provada insatisfatível pelo solucionador SAT. Isso significa que não existe uma atribuição de valores em $\{-4, \dots, 4\}$ que satisfaça as condições. Um fluxo não nulo de valor 6 ($nz6$) é possível, mas o de valor 5 não.

Contraexemplo 2: Construção de 36 pontos baseada em aritmética de raízes quadradas

• Construção: Utiliza parâmetros específicos ($v_1=1, v_2=3, w=2$) para gerar coordenadas da forma $\sqrt{|w_1\sqrt{v_1} + w_2\sqrt{v_2}|}$. Após filtrar triplas que formam pontos na esfera e podar o grafo resultante, obtém-se um subconjunto mínimo.
• Resultado: Um conjunto de 36 pontos e 13 triplas.
• Verificação: A fórmula CNF (144 variáveis, 6.710 cláusulas) também foi provada insatisfatível para valores em $\{-4, \dots, 4\}$. Novamente, apenas um fluxo $nz6$ (valores $\pm 5$ incluídos) é viável.

4. Significado e Implicações

• Refutação da Conjectura 1.2: O trabalho demonstra definitivamente que a Conjectura 1.2 de Jain é falsa. Não é possível mapear toda a esfera $S^2$ (ou mesmo certos subconjuntos finitos críticos) para o conjunto $\{-4, \dots, 4\}$ satisfazendo as condições de soma zero em grandes círculos.
• Impacto na Conjectura de Tutte: Como a Conjectura 1.2 é um componente necessário para provar a Conjectura do Fluxo 5 de Tutte via a abordagem de Jain, sua refutação indica que essa rota específica de prova não funcionará da forma proposta.
• Novas Questões Abertas:
  • É possível encontrar subconjuntos que exijam valores $\pm 6$ ou superiores? (Até agora, $\pm 5$ foi o máximo necessário).
  • Qual é o menor subconjunto possível que serve como contraexemplo?
  • Existe algum subconjunto (possivelmente infinito ou com propriedades algébricas específicas) que ainda permita um fluxo $nz5$ e seja útil para conectar a Conjectura 1.1 à de Tutte?
• Observação sobre Fluxos Modulares: O autor nota que, em todos os experimentos, não houve diferença entre fluxos não nulos $k$ e fluxos não nulos módulo $k$ quanto ao valor mínimo de $k$ necessário, levantando uma questão teórica interessante sobre a equivalência desses conceitos.

O código-fonte, incluindo as codificações SAT, buscas por backtracking e verificações formais em Lean 4, está disponível publicamente no repositório GitHub do autor.