Planar-Toroidal Decomposition of $K_{12}$

Este artigo demonstra, através de argumentos teóricos e uma busca computacional, que não é possível decompor o grafo completo $K_{12}$ em um subgrafo planar e um toroidal, além de identificar todas as 123 configurações únicas onde o subgrafo toroidal possui apenas duas arestas a menos que o complemento do grafo planar.

O essencial

Imagine que você tem um quebra-cabeça gigante feito de 66 peças (as arestas de um gráfico completo com 12 pontos). O desafio proposto por matemáticos em 1978 era: será que é possível dividir esse quebra-cabeça em duas partes perfeitas?

Uma parte teria que ser desenhável em uma folha de papel plana (sem que as linhas se cruzem). A outra parte teria que ser desenhável na superfície de uma toro (o formato de uma rosquinha ou uma bola de beisebol furada).

Os autores deste artigo, Allan Bickle e Russell Campbell, decidiram resolver esse mistério. A resposta curta? Não é possível. Eles provaram matematicamente e com a ajuda de computadores que esse "casamento perfeito" entre uma folha de papel e uma rosquinha para 12 pontos não existe.

Aqui está a explicação detalhada, usando analogias simples:

1. O Cenário: A Folha de Papel vs. A Rosquinha

Pense em um gráfico como uma rede de cidades (pontos) conectadas por estradas (linhas).

• Gráfico Planar: É como desenhar um mapa de estradas em uma folha de papel plana. Se você tentar conectar todas as cidades possíveis entre si, as estradas inevitavelmente vão se cruzar, a menos que você tenha poucas cidades. Para 12 cidades, o número de cruzamentos seria enorme.
• Gráfico Toroidal: É como desenhar o mesmo mapa, mas agora você pode usar uma rosquinha. Na rosquinha, você pode passar uma estrada "por dentro" do buraco ou "por cima" da rosquinha para evitar cruzamentos. Isso permite conectar muito mais cidades sem que as linhas se toquem.

O problema era: Se pegarmos todas as conexões possíveis entre 12 cidades, podemos separá-las em dois grupos?

• Grupo A: Todas as estradas cabem na folha de papel.
• Grupo B: Todas as estradas restantes cabem na rosquinha.

2. A Investigação: Como eles descobriram a resposta?

Os matemáticos usaram duas abordagens, como se fossem detetives:

A. A Abordagem Teórica (A Lógica)

Eles olharam para as "regras do jogo" antes mesmo de ligar o computador.

• O Limite de Estradas: Uma folha de papel tem um limite rígido de quantas estradas pode ter antes de ficar bagunçada. Uma rosquinha aguenta um pouco mais.
• O "Ponto de Equilíbrio": Para que a divisão funcione, o gráfico de papel precisaria ser "maximamente cheio" (como uma rede de arame farpado perfeita) e o gráfico da rosquinha também precisaria estar quase cheio.
• O Problema dos Cruzamentos: Eles descobriram que, se você tentar forçar o gráfico de papel a ter o máximo de conexões, ele cria "buracos" ou estruturas que são impossíveis de esconder na rosquinha. É como tentar encaixar uma peça de Lego quadrada em um buraco redondo: por mais que você gire, não encaixa.

Eles provaram que, se houver um gráfico de papel perfeito com 12 pontos, o que sobrar para a rosquinha sempre terá "muitas arestas a mais" do que a rosquinha consegue suportar sem cruzamentos.

B. A Abordagem Computacional (A Varredura)

Como a lógica teórica não eliminou todas as possibilidades, eles precisaram de força bruta.

• O Banco de Dados: Existem 7.595 maneiras diferentes de desenhar um gráfico de 12 pontos em uma folha de papel sem cruzamentos (chamados de "triangulações planas").
• A Varredura: Eles usaram um computador para pegar cada uma dessas 7.595 redes de papel, calcular o que sobraria (o "complemento") e tentar desenhar esse resto na rosquinha.
• O Resultado: O computador rodou por semanas. Em nenhum dos 7.595 casos, o resto coube na rosquinha.
  • Curiosidade: O computador encontrou 123 casos onde o resto quase coube na rosquinha, mas faltava apenas duas estradas para que funcionasse. Se você tirasse duas conexões extras, daria certo. Mas com todas as conexões originais, é impossível.

3. Por que isso importa? (O Significado)

Este trabalho resolve um quebra-cabeça antigo que durou quase 50 anos.

• Desmentindo uma Aposta: Existia uma conjectura (uma aposta matemática) de que, para qualquer número grande de pontos, sempre seria possível fazer essa divisão. Este artigo mostra que, para 12 pontos, essa aposta está errada.
• A Fronteira do Conhecimento: Eles descobriram que a "toro" é um pouco mais fraca do que se pensava para esse tamanho específico. É como descobrir que, embora a rosquinha seja um ótimo lugar para desenhar mapas, ela tem um limite de capacidade que, para 12 cidades, não é suficiente para absorver o excesso de conexões que sobra da folha de papel.

Resumo em uma frase

Os autores provaram que, para um grupo de 12 pontos, é impossível dividir todas as conexões possíveis em um mapa plano e um mapa de rosquinha; a rosquinha sempre ficará "sobrecarregada" com conexões demais, a menos que você remova algumas delas.

É um triunfo da matemática combinada com a computação moderna, mostrando que, às vezes, a resposta para um problema complexo é simplesmente: "Não, não dá para fazer isso".

Resumo técnico

Aqui está um resumo técnico detalhado do artigo "Planar-Toroidal Decomposition of K12" (Decomposição Plana-Toroidal de K12), escrito por Allan Bickle e Russell Campbell, apresentado em português.

1. O Problema

O artigo aborda uma questão fundamental na teoria dos grafos e topologia, proposta originalmente por Anderson e White em 1978: é possível decompor o grafo completo de 12 vértices ($K_{12}$) em dois subgrafos, sendo um planar e o outro toroidal?

Este problema está diretamente ligado à determinação do valor de $N(0, 1)$, definido como o menor tamanho de um grafo completo que não pode ser particionado em arestas em duas partes, uma embutível na esfera (planar, gênero 0) e outra no toro (gênero 1).

• Sabia-se que $N(0, 0) = 9$ (decomposição em dois planos) e $N(1, 1) = 14$ (decomposição em dois toros).
• A conjectura de Bickle e White (2013) sugeriu que para $n=12$, existiria um grafo $G$ tal que $\gamma(G) + \gamma(\bar{G}) = 1$, o que implicaria a existência dessa decomposição. O objetivo deste trabalho foi verificar essa possibilidade especificamente para $n=12$.

2. Metodologia

Os autores empregaram uma abordagem híbrida, combinando argumentos teóricos rigorosos com uma busca computacional exaustiva.

Abordagem Teórica

Os autores desenvolveram três métodos teóricos para eliminar casos potenciais de grafos planares maximais de ordem 12 cujos complementos poderiam ser toroidais:

1. Graus dos Vértices: Utilizaram limites de arestas para grafos planares ($m \le 3n-6$) e toroidais ($m \le 3n$). Para $n=12$, ambos os fatores de uma decomposição ideal deveriam ter o número máximo de arestas. Isso levou a restrições nos graus dos vértices ($\delta(G) \ge 3, \Delta(G) \le 8$) e propriedades de independência para vértices de grau 8.
2. Contagem de Triângulos: Aplicaram fórmulas de Goodman e Sauvé para relacionar o número de triângulos em um grafo $G$ e seu complemento $\bar{G}$. Como um grafo planar maximal de ordem 12 tem 20 triângulos e um triangulação toroidal precisa de pelo menos 24, eles eliminaram sequências de graus que não satisfaziam a soma mínima necessária de triângulos.
3. Conjuntos de Separação: Analisaram a estrutura de triângulos e ciclos de separação. Demonstraram teoremas que proíbem certos tipos de separação (ex: um triângulo de separação que deixa subgrafos de ordens 3 e 6, ou um ciclo de 4 vértices que deixa dois subgrafos de ordem 4), pois tais configurações forçariam a existência de subgrafos com gêneros incompatíveis (como $K_{3,6}$ ou $K_{4,4}$) que não podem ser embutidos no toro sem cruzamentos.

Abordagem Computacional

Apesar das eliminações teóricas, a busca foi concluída computacionalmente devido à complexidade dos algoritmos de embutimento no toro (que são mais complexos que os de planaridade):

• Base de Dados: Utilizaram a lista completa de 7.595 grafos planares maximais (triangulações) de ordem 12, disponíveis no Combinatorial Object Server.
• Filtragem: Eliminaram grafos com grau máximo $\ge 9$ e aqueles que violavam as condições de conjuntos independentes de vértices de grau 8.
• Busca de Embutimento:
  1. Verificaram se o complemento de qualquer triangulação planar restante podia ser embutido no toro (nenhum foi encontrado).
  2. Testaram a remoção de uma aresta do complemento (nenhum embutimento encontrado).
  3. Testaram a remoção de duas arestas de cada complemento. Esta foi a etapa mais custosa, levando cerca de 59 dias de processamento.
• Validação: O código foi escrito em C/C++ para gerar visualizações e verificar isomorfismos, removendo duplicatas e identificando configurações únicas.

3. Resultados Principais

Os resultados do estudo são conclusivos e negativos para a existência da decomposição perfeita:

1. Inexistência de Decomposição: Não existe nenhuma decomposição de $K_{12}$ em um grafo planar e um grafo toroidal. Portanto, $N(0, 1) = 12$.
2. Refutação da Conjectura: O trabalho refuta a Conjectura 1.5 de Bickle/White para o caso $n=12$, mostrando que não há grafo $G$ de ordem 12 tal que $\gamma(G) + \gamma(\bar{G}) = 1$.
3. Limite de Arestas: Foi provado que se $G$ é planar de ordem 12 e $H \subseteq G$ é toroidal, então $H$ deve ter pelo menos duas arestas a menos que $G$ (ou seja, o complemento de um planar maximal não é toroidal, nem mesmo removendo uma aresta).
4. Casos de Quase-Decomposição: A busca computacional identificou exatamente 123 pares únicos $(G, H)$ onde $G$ é uma triangulação planar de ordem 12 e $H$ é o complemento de $G$ com duas arestas removidas, permitindo que $H$ seja embutido no toro.
   • O artigo fornece visualizações e dados detalhados desses 123 casos (incluindo exemplos nas Figuras 1 e 2 do artigo).

4. Significado e Contribuições

• Resolução de um Problema Aberto: O artigo resolve definitivamente uma questão de mais de 40 anos sobre a decomposição de $K_{12}$, estabelecendo o limite exato para $N(0, 1)$.
• Avanço em Algoritmos de Embutimento: O trabalho destaca a dificuldade atual de algoritmos de embutimento no toro (não existindo implementações lineares livres de erros) e demonstra a eficácia de buscas exaustivas combinadas com filtragem teórica para superar essa limitação.
• Recursos para a Comunidade: Os autores disponibilizaram publicamente:
  • Uma lista de 123 embutimentos toroidais únicos (com duas arestas removidas).
  • Imagens procedurais de todas as 7.595 triangulações planares de ordem 12.
  • Código-fonte e scripts para geração de dados, hospedados em um repositório GitHub.
• Implicações Teóricas: Os resultados fornecem novos limites e contra-exemplos para a soma e produto dos gêneros de grafos e seus complementos, refinando o entendimento da relação entre planaridade e toroidalidade em grafos completos.

Em suma, o paper demonstra que, embora $K_{12}$ possa ser decomposto em dois grafos toroidais, ele não pode ser decomposto em um planar e um toroidal, exigindo a remoção de pelo menos duas arestas do complemento planar para atingir a embedabilidade toroidal.