Graph Puzzles III.1: A Proof of Sabidussi's Compatibility Conjecture

Resumen Técnico: Una Prueba de la Conjetura de Compatibilidad de Sabidussi

Planteamiento del Problema
El artículo aborda la conjetura de compatibilidad de Sabidussi en el contexto de multigrafos conexos finitos. Específicamente, considera un multigrafo Euleriano $G$ (donde cada vértice tiene grado par) con un grado mínimo $\delta(G) \geq 4$. Dada una trayectoria cerrada $T$ que atraviesa cada arista exactamente una vez (un recorrido Euleriano), el problema pregunta si las aristas de $G$ pueden particionarse en circuitos (subgrafos conexos 2-regulares) de tal manera que ningún circuito contenga dos aristas que aparezcan consecutivamente en $T$.

En el lenguaje de los sistemas de transición, un recorrido Euleriano induce un emparejamiento de semiaristas en cada vértice. Una descomposición de circuitos es "compatible" si ningún circuito empareja semiaristas que han sido prescritas como una transición por el recorrido. La conjetura afirma que tal descomposición compatible siempre existe bajo las restricciones de grado dadas.

Metodología
La prueba procede mediante una reducción del problema de la teoría de grafos a un problema combinatorio de palabras cíclicas, seguido de una construcción algebraica utilizando argumentos de paridad sobre el cuerpo $\mathbb{F}_2$.

1. Reducción a Palabras Cíclicas:
   Los autores definen una palabra cíclica $w = (v_0, v_1, \dots, v_{m-1})$ que representa la secuencia de vértices visitados por el recorrido Euleriano $T$. Las aristas del recorrido corresponden a "huecos" entre estas letras. El problema se reformula como la búsqueda de una coloración de estos huecos con elementos de $\mathbb{F}_2^2$ (una 4-coloración) de tal manera que:

   • Los huecos adyacentes (correspondientes a aristas consecutivas en el recorrido) reciban colores diferentes.
   • Para cada vértice $v$ en el grafo, los colores asignados a los huecos incidentes con las ocurrencias de $v$ satisfagan una condición de paridad: cada color aparece un número par de veces entre las incidencias de los huecos.

2. Marco Algebraico:
   El núcleo de la prueba se basa en dos lemas establecidos en la Sección 3:

   • Lema 3.1 (Paridad de cuatro colores): Una familia de elementos en $\mathbb{F}_2^2$ contiene cada elemento un número par de veces si y solo si su suma lineal es cero y su suma cuadrática (definida mediante una forma bilineal específica $q(x) = x_1x_2$) es cero.
   • Lema 3.2 (Equilibrio de tres estados): Un principio de selección global que establece que para un conjunto finito $U$ y un conjunto de tres elementos $\Sigma$, si ciertas condiciones de simetría y suma cero son cumplidas por una función $\beta$, el número de asignaciones que satisfacen un sistema de restricciones locales es impar (y, por lo tanto, no nulo).

3. Construcción de la Coloración:
   La prueba construye la coloración de huecos requerida mediante:

   • La definición de "patrones locales" $\Delta_{a,t}$ para cada letra $a$ en la palabra cíclica, que asignan valores no nulos en $\mathbb{F}_2^2$ a las ocurrencias de $a$ de tal manera que su suma sea cero.
   • La definición de términos de interacción $\beta_{ab}$ entre distintas letras basadas en el orden de sus ocurrencias en la palabra.
   • La aplicación del Lema 3.2 para seleccionar un estado específico $t_a \in \Omega$ (donde $\Omega = \mathbb{F}_2^2 \setminus \{0\}$) para cada letra $a$. Esta selección asegura que las restricciones de interacción desaparezcan.
   • El uso de estas selecciones para definir una secuencia $y_i$ (diferencias entre colores de huecos) e integrarlas para recuperar los colores de los huecos $x_i$.
   • La verificación de que la coloración resultante satisface la condición de grado par para cada clase de color en cada vértice, mostrando que la suma de los colores y la suma de sus formas cuadráticas se anulan, invocando el Lema 3.1.

Contribuciones y Resultados Clave

• Teorema 1.1: El artículo demuestra que para cualquier multigrafo Euleriano finito con grado mínimo al menos de 4 y cualquier recorrido Euleriano $T$, existe una coloración $\chi: E(G) \to \mathbb{F}_2^2$ tal que las aristas consecutivas en $T$ tienen colores diferentes, y cada vértice tiene grado par en cada clase de color.
• Corolario 1.2: Como consecuencia, el grafo $G$ admite una descomposición de circuitos compatible con el sistema de transición inducido por $T$.
• Mejora en la Doble Cobertura de Ciclos: El artículo señala que, en presencia de un circuito dominante, el resultado implica que un grafo cúbico $H$ tiene una doble cobertura de 5 ciclos que contiene dicho circuito. Esto mejora el teorema de la doble cobertura de 8 ciclos recientemente probado (atribuido a OpenAI en el texto) para grafos con un circuito dominante.
• Formalización: La prueba ha sido totalmente formalizada en el demostrador de teoremas Lean.

Significancia y Reivindicaciones
El artículo afirma proporcionar una prueba completa de la conjetura de compatibilidad de Sabidussi, un problema que ha sido estudiado desde el trabajo de Kotzig (1968) y Fleischner (1980). Si bien resultados previos habían establecido la conjetura para grafos planares, grafos libres de menor $K_5$, o restricciones de grado específicas, esta prueba trata cada grado par directamente sin restringir la clase de grafos más allá del requisito de grado mínimo.

Los autores afirman explícitamente que la prueba es un fortalecimiento de la conjetura original, proporcionando una 4-coloración con propiedades estructurales específicas en lugar de solo una descomposición. El trabajo se presenta como una resolución definitiva a la conjetura, apoyándose en una novedosa combinación de combinatoria de palabras cíclicas y lemas de paridad sobre cuerpos finitos.

Nota sobre la Autoría
El artículo establece explícitamente que la prueba se debe enteramente a "GPT 5.6 Pro", y que el escrito fue preparado con la asistencia de "GPT 5.6 Sol". El autor humano, Nikolay Ulyanov, reconoce el papel de la IA en la generación del argumento matemático y la exposición.