Planar-Toroidal Decomposition of $K_{12}$

Mediante argumentos teóricos y una búsqueda computacional, este artículo demuestra que no existe una descomposición del grafo completo $K_{12}$ en un subgrafo plano y uno toroidal, y además identifica las 123 parejas únicas que minimizan la diferencia de aristas entre el complemento del grafo plano y el subgrafo toroidal.

Lo esencial

Imagina que tienes un grupo de 12 amigos y quieres organizar una fiesta donde todos se saluden entre sí. En matemáticas, esto se llama un "grafo completo" (todos conectados con todos). El problema que resuelve este artículo es intentar dividir a estos 12 amigos en dos grupos de conexiones diferentes, siguiendo reglas muy estrictas:

1. Grupo A (Planar): Las conexiones de este grupo deben poder dibujarse en una hoja de papel plana (como un mapa de la Tierra) sin que ninguna línea se cruce con otra. Imagina que es un mapa de carreteras donde no hay puentes ni túneles; todo está en el suelo.
2. Grupo B (Toroide): Las conexiones restantes deben poder dibujarse en la superficie de una taza de café con asa (un toro). Aquí, las líneas pueden "atravesar" el agujero de la taza, lo que permite conexiones que serían imposibles en una hoja de papel plana.

El Gran Misterio

En 1978, dos matemáticos (Anderson y White) se preguntaron: "¿Es posible dividir a estos 12 amigos exactamente en dos grupos así? Uno que quepa en una hoja de papel y otro que quepa en una taza de café, sin que sobre ni falte ninguna conexión?"

La respuesta que dan los autores de este artículo (Allan Bickle y Russell Campbell) es un rotundo NO.

¿Cómo lo descubrieron?

Para resolver este rompecabezas, usaron una combinación de lógica de detective y una búsqueda masiva en computadora.

1. La Lógica (El Detective)

Primero, usaron reglas matemáticas para descartar muchas posibilidades sin necesidad de revisarlas una por una.

• La regla de los grados: Imagina que cada amigo tiene un número de "amigos cercanos" en el Grupo A. Si alguien tiene demasiados amigos en el Grupo A, el Grupo B se vuelve demasiado complicado para caber en la taza. Los matemáticos demostraron que si intentas forzar esta división, siempre te encuentras con una contradicción, como intentar meter un elefante en un frasco de mermelada.
• Los triángulos: En estos dibujos, los triángulos son como las "piezas de un rompecabezas". Contaron cuántos triángulos podían formarse y descubrieron que, para 12 personas, la geometría simplemente no encaja. Es como intentar armar un cubo perfecto usando piezas que siempre tienen un lado redondo.

2. La Búsqueda Computacional (El Explorador)

Como la lógica no descartó absolutamente todo, tuvieron que ser exhaustivos.

• El inventario: Sabían que existen 7,595 formas diferentes de conectar a 12 personas en un mapa plano (sin cruces). Es como tener 7,595 mapas de carreteras únicos.
• La prueba de fuego: Escribieron un programa de computadora que revisó cada uno de esos 7,595 mapas. Para cada mapa, tomó las conexiones que no estaban en él y trató de dibujarlas en una taza de café (un toro).
• El resultado: La computadora trabajó durante semanas. El resultado final fue: Ninguno funcionó. No importa cómo intentes dibujar el mapa plano, las conexiones que sobran nunca encajan perfectamente en la superficie de la taza.

El Hallazgo Sorprendente

Aunque no pudieron encontrar una solución perfecta (donde las conexiones sobrantes encajen exactamente en la taza), encontraron algo muy interesante:

• Si tomas un mapa plano perfecto y le quitas dos líneas (dos conexiones) de las que sobran, ¡entonces sí puedes dibujar el resto en la taza!
• Encontraron 123 casos únicos donde esto sucede. Es como si la taza de café tuviera un agujero muy pequeño que necesita que le quites dos "cables" extra para que todo encaje.

¿Por qué importa esto?

Este artículo es importante porque:

1. Resuelve un misterio antiguo: Cierra la puerta a la idea de que se puede dividir a 12 personas en un grupo plano y uno toroidal perfectamente.
2. Descarta una conjetura: Había una teoría (una conjetura) que sugería que esto era posible para ciertos números. Este trabajo demuestra que la teoría falla específicamente cuando hay 12 personas.
3. Ayuda a futuros matemáticos: Al mostrar exactamente qué no funciona y encontrar los casos más cercanos (los 123 donde faltan solo dos líneas), les dan a otros investigadores un mapa de dónde buscar y qué evitar.

En resumen: Los autores demostraron que, aunque la geometría es flexible, tiene límites. Con 12 personas, no puedes dividir sus conexiones en un "mapa plano" y un "mapa de taza" perfectamente. La naturaleza de las matemáticas exige que, en este caso, siempre sobre un poco de "caos" que no encaja en ninguna de las dos formas.

Resumen técnico

Aquí tienes un resumen técnico detallado del artículo "Planar-Toroidal Decomposition of K12" (Descomposición Planar-Toroidal de K12), presentado en español.

Resumen Técnico: Descomposición Planar-Toroidal de K12

Autores: Allan Bickle y Russell Campbell.
Publicación: Discrete Mathematics and Theoretical Computer Science, Vol. 28:2 #3 (2026).

1. El Problema y el Contexto

El artículo aborda una pregunta abierta planteada en 1978 por Anderson y White: ¿Existe una descomposición del grafo completo $K_{12}$ en dos subgrafos, uno planar y otro toroidal?

Este problema está intrínsecamente ligado al concepto de espesor (thickness) y a la función $N(\gamma, \gamma')$, que define el tamaño del grafo completo más pequeño que no puede particionarse en dos subgrafos embebibles en superficies de género $\gamma$ y $\gamma'$ respectivamente.

• Se sabe que $N(0,0) = 9$ (dos planos).
• Se sabe que $N(1,1) = 14$ (dos toros).
• La pregunta específica es determinar $N(0,1)$. Si $K_{12}$ pudiera descomponerse en un plano y un toro, entonces $N(0,1) > 12$. De lo contrario, $N(0,1) = 12$.

Además, el trabajo refuta una conjetura de Bickle y White (2013) que sugería que para todo $n \ge 11$, la cota inferior de la suma de los géneros de un grafo y su complemento, $\gamma(G) + \gamma(\bar{G})$, se alcanza. Para $n=12$, la conjetura predecía que existiría un grafo con $\gamma(G) + \gamma(\bar{G}) = 1$ (es decir, uno planar y uno toroidal).

2. Metodología

Los autores emplearon un enfoque híbrido que combina argumentos teóricos para reducir el espacio de búsqueda y una búsqueda computacional exhaustiva para verificar los casos restantes.

A. Enfoques Teóricos (Filtrado de Casos):
Se analizaron tres estrategias para descartar grafos candidatos sin necesidad de búsqueda computacional completa:

1. Grados de los Vértices:
   • Se establecieron límites estrictos para los grados mínimos ($\delta$) y máximos ($\Delta$) en un grafo planar maximal ($G$) y su complemento toroidal ($\bar{G}$).
   • Se demostró que si existe tal descomposición, $3 \le \delta(G) \le 5$y$5 \le \Delta(G) \le 8$.
   • Se identificaron secuencias de grados específicas que son imposibles basándose en la fórmula de conteo de triángulos de Goodman.
2. Conteo de Triángulos:
   • Utilizando la fórmula de Goodman, se calculó el número total de triángulos en $G$ y $\bar{G}$.
   • Dado que un grafo planar maximal de orden 12 tiene 20 triángulos y un toro maximal requiere al menos 24, se descartaron secuencias de grados que no permitían alcanzar esta suma mínima.
3. Conjuntos de Separación (Separating Sets):
   • Se analizaron triángulos separadores y ciclos separadores.
   • Se demostró teóricamente que si $G$ tiene un triángulo separador que deja subgrafos de orden 3 y 6, o un ciclo separador de 4 vértices que deja dos subgrafos de orden 4, se generan contradicciones topológicas (como la necesidad de embeber $K_{3,6}$ o $K_{4,4}$ de formas no compatibles con la planaridad o la toroidalidad).

B. Búsqueda Computacional Exhaustiva:
Dado que los filtros teóricos no eliminaron todos los casos posibles, se procedió a una búsqueda computacional masiva:

• Base de Datos: Se utilizaron los 7,595 grafos triangulares maximales (planos) de orden 12 disponibles en el Combinatorial Object Server.
• Filtrado Inicial: Se eliminaron 3,476 grafos con grado máximo $\Delta > 8$ y aquellos que violaban las condiciones de independencia de vértices de grado 8.
• Algoritmo de Búsqueda:
  1. Se verificó si el complemento de cada grafo triangular restante admitía una embebición en el toro. (Resultado: Ninguno).
  2. Se probaron eliminaciones de una arista del complemento. (Resultado: Ninguno).
  3. Se probaron eliminaciones de dos aristas del complemento. Esta fue la búsqueda más intensiva, tomando aproximadamente 59 días de tiempo de cómputo.
• Herramientas: Se utilizó código personalizado en C/C++ para la generación de imágenes y la búsqueda de embebiciones, junto con herramientas como Surftri para generar triangulaciones.

3. Resultados Principales

1. Inexistencia de la Descomposición:
   El resultado central del trabajo es la demostración de que no existe una descomposición de $K_{12}$ en un grafo planar y un grafo toroidal.

   • Esto implica que $N(0, 1) = 12$. Es decir, $K_{12}$ es el grafo completo más pequeño que no puede particionarse en un plano y un toro.

2. Refutación de la Conjetura:
   Al demostrar que no existe tal grafo $G$ para $n=12$, se refuta la Conjetura 1.5 de Bickle/White para este caso específico. No existe un grafo de orden 12 tal que $\gamma(G) + \gamma(\bar{G}) = 1$.

3. Caso de Equidad (Casi-Descomposición):
   Aunque la descomposición exacta no es posible, los autores encontraron casos "cercanos":

   • Si $G$ es planar de orden 12 y $H \subseteq G$ es toroidal, entonces $H$ debe tener al menos dos aristas menos que $G$.
   • La búsqueda computacional identificó exactamente 123 pares únicos $(G, H)$ donde la diferencia es exactamente de dos aristas. En estos casos, el complemento de $G$ se puede embeber en un toro si se eliminan dos aristas.
   • Se proporcionan ejemplos visuales de estas configuraciones en las Figuras 1 y 2 del artículo.

4. Contribuciones y Significancia

• Resolución de un Problema Abierto: Cierra una pregunta de casi 50 años sobre la descomposición de grafos completos en superficies de género 0 y 1.
• Avance en la Teoría de Espesor: Proporciona un valor exacto para $N(0,1)$, completando el panorama de los valores de espesor para pares de superficies $(0,0), (1,1), (2,2)$ y ahora $(0,1)$.
• Método Híbrido: El artículo sirve como un modelo de cómo combinar restricciones teóricas fuertes (grados, triángulos, conjuntos de separación) con búsquedas computacionales exhaustivas para resolver problemas de teoría de grafos que son intratables por pura deducción o por fuerza bruta pura.
• Recursos Abiertos: Los autores han hecho públicos los datos generados, incluyendo:
  • La lista de 123 pares únicos encontrados.
  • Imágenes de las 7,595 triangulaciones planas de orden 12.
  • Código fuente y scripts para la generación y verificación, alojados en un repositorio de GitHub.
• Validación de Algoritmos: El trabajo destaca la complejidad de los algoritmos de embebición toroidal (que carecen de implementaciones lineales libres de errores) y valida la necesidad de búsquedas exhaustivas para verificar casos críticos.

En conclusión, el paper demuestra que la estructura combinatoria de $K_{12}$ es demasiado densa para ser dividida limpiamente entre una esfera y un toro, estableciendo un límite fundamental en la teoría de descomposición de grafos.