LIGUE CADA PONTO A TODOS OS OUTROS: O MENOR NÚMERO DE CRUZAMENTOS, DEMONSTRADO

Coloque cinco pontos numa folha de papel e ligue cada par com uma curva: dez curvas ao todo. Elas podem se curvar como você quiser, mas nenhuma pode passar por um terceiro ponto. Tente evitar todos os cruzamentos e você vai fracassar. Com cinco pontos, pelo menos 1 cruzamento é inevitável; com seis, pelo menos 3; com dez, pelo menos 60.

Os matemáticos chamam essa figura de desenho do grafo completo Kₙ — n pontos, cada par ligado — e o menor número de cruzamentos que um desenho pode atingir de seu número de cruzamentos. Martin Balko, da Universidade Carolina, na República Tcheca, chama a questão de “um dos problemas mais famosos da teoria topológica dos grafos”.

A contagem de um artista

No fim dos anos 1950, o artista britânico Anthony Hill construiu desenhos de Kₙ com exatamente

Z(n) = ¼ ⌊n/2⌋ ⌊(n − 1)/2⌋ ⌊(n − 2)/2⌋ ⌊(n − 3)/2⌋

cruzamentos, em que ⌊ ⌋ significa arredondar para baixo. A suposição de que nenhum desenho pode fazer melhor foi publicada primeiro por Guy, depois discutida por Harary e Hill, e popularizada por Erdős e Guy. Ela é conhecida como conjectura de Harary–Hill, ou conjectura de Guy.

A fórmula cresce depressa:

• 4 pontos ou menos: 0 cruzamentos
• 5 pontos: 1
• 7 pontos: 9
• 10 pontos: 60
• 14 pontos: 315

Seis décadas de respostas parciais

Desenhos com exatamente Z(n) cruzamentos existiam para qualquer número de pontos; a parte difícil era mostrar que nenhum desenho faz melhor.

Por mais de sessenta anos, isso só foi provado para tipos especiais de desenhos — por exemplo, com todos os pontos numa reta e cada curva mantida de um lado dela, ou com os pontos numa esfera e cada curva seguindo o caminho mais curto. O próprio Balko, com Fulek e Kynčl, tinha resolvido uma dessas classes. Em 2021, computadores tinham confirmado a fórmula até 14 pontos. Para números muito grandes de pontos, os melhores resultados gerais garantiam pelo menos 98,5%, depois 98,99%, de Z(n).

Uma prova, depois uma mais clara

Em 2026, a OpenAI anunciou uma prova para qualquer número de pontos, que o artigo de Balko cita como um “OpenAI Math Release preprint” e à qual atribui o teorema. O artigo não diz como essa prova foi encontrada. Nas palavras de Balko, a original “é relativamente curta”, mas “bastante difícil de acompanhar”. Seu preprint apresenta uma variante simplificada que, escreve ele, “exige apenas conhecimentos elementares de álgebra linear e teoria dos grafos”. Outro matemático, Gelasio Salazar, prepara uma exposição separada e detalhada.

Contar coeficientes em vez de cruzamentos

Como desenhos conhecidos já atingem Z(n), só o limite inferior precisa ser provado. São quatro passos.

1. Números ímpares bastam. Um desenho ótimo pode ser redesenhado de modo que curvas que compartilham um ponto nunca se cruzem; cada cruzamento passa então a envolver 4 pontos diferentes. Apague cada um dos 6 pontos, um de cada vez: cada figura restante de 5 pontos tem pelo menos 1 cruzamento, e cada cruzamento sobrevive a exatamente 2 das 6 remoções (ele desaparece sempre que um de seus próprios 4 pontos é apagado, e sobrevive às outras 2). Logo, o dobro dos cruzamentos é pelo menos 6: pelo menos 3, que é Z(6). A mesma contagem funciona para qualquer número par.
2. Uma família de polinômios. Dê a cada ponto seu próprio número. Um cruzamento envolve duas curvas, portanto quatro pontos, portanto quatro números. Balko usa polinômios em quatro variáveis, escolhidos para que a família tenha exatamente Z(n) coeficientes independentes quando n é ímpar — para 7 pontos, 3 × 3 = 9.
3. Poucos cruzamentos deixam folga. Exigir que um polinômio se anule num cruzamento é uma equação. Com menos equações do que coeficientes livres, a álgebra linear sempre deixa uma solução não nula. Assim, um desenho com menos de Z(n) cruzamentos viria acompanhado de um polinômio não nulo que se anula em todos os seus cruzamentos; tome o de menor grau.
4. O plano resiste. A geometria entra por meio de um fato clássico: um laço fechado no plano cruza outro da direita para a esquerda exatamente tantas vezes quanto da esquerda para a direita. Com pesos bem escolhidos, isso fornece uma soma de quadrados dos valores do polinômio, alguns contados positivamente, outros negativamente, cujo total é zero. Os termos positivos ficam todos em cruzamentos, onde o polinômio é zero, então os negativos também precisam se anular. Um segundo uso do fato sobre laços o torna divisível por um fator fixo; dividindo, obtém-se um polinômio não nulo de grau menor com a mesma propriedade, o que é impossível, já que tomamos o de menor grau.

Esse argumento de sinais é a principal mudança de Balko: ele substitui o argumento original “envolvendo uma forma bilinear não degenerada e complementos ortogonais”. Ele também prova o fato sobre laços de outro modo e isola cada ponto de forma mais direta.

Outras redes resolvidas de uma vez

A resposta continua sendo Z(n) se contarmos, em vez dos cruzamentos, os pares de curvas que se cruzam pelo menos uma vez, ou que se cruzam um número ímpar de vezes — desde que curvas que compartilham um ponto nunca se encontrem em outro lugar. Combinado com reduções anteriores, o teorema também dá os números de cruzamentos exatos de grafos completos com algumas ligações removidas, de cópias de um grafo completo encadeadas ao longo de um caminho ou em volta de um ciclo par, e de uma família de redes de aspecto fractal chamadas grafos de Sierpiński estendidos.

Retire uma única curva do grafo completo de 6 pontos e seu mínimo cai de 3 cruzamentos para 2; com 8 pontos, de 18 para 15.