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

Este artículo presenta dos contraejemplos que refutan la segunda conjetura de Jain sobre flujos de vectores unitarios, demostrando que ciertas configuraciones de puntos en la esfera requieren valores fuera del conjunto $\{-4, \dots, 4\}$ originalmente propuesto.

Lo esencial

¡Hola! Vamos a desglosar este paper matemático complejo y transformarlo en una historia que cualquiera pueda entender, usando analogías de la vida cotidiana. Imagina que las matemáticas son como un gran rompecabezas de lógica y geometría.

El Gran Rompecabezas: ¿Puedes colorear el mundo sin romperlo?

Imagina que tienes una red de carreteras (un "grafo") que conecta muchas ciudades. El problema matemático que nos ocupa es: ¿Es posible asignar una dirección y una fuerza a cada carretera de tal manera que el tráfico fluya perfectamente sin que ninguna carretera se quede vacía?

En matemáticas, esto se llama un "flujo". Los matemáticos han estado discutiendo durante décadas si siempre es posible hacer esto con números del 1 al 5 (un "flujo 5").

La Hipótesis de Jain: El Truco del "Globo Mágico"

Hace un tiempo, un matemático llamado K. Jain propuso una idea brillante para resolver este problema. Dijo: "Oye, en lugar de usar números simples, usemos vectores (flechas) que apunten a un globo terráqueo imaginario (una esfera)".

Su teoría tenía dos partes:

1. La Parte 1: Creía que para cualquier red de carreteras sin "callejones sin salida" (puentes), siempre podrías asignar una flecha unitaria (de tamaño 1) a cada carretera.
2. La Parte 2 (La que este paper ataca): Propuso que podrías pintar los puntos de ese globo terráqueo con números del -4 al 4 (excluyendo el cero), siguiendo reglas muy estrictas:
   • Si un punto tiene el color "3", su opuesto exacto en el globo debe tener el color "-3".
   • Si tomas tres puntos que forman un triángulo perfecto en el globo (como los vértices de un triángulo equilátero), sus números deben sumar cero (ej: 1 + 2 + (-3) = 0).

Si esto fuera cierto, ¡habríamos resuelto el misterio de los flujos 5! Sería como tener un mapa universal que garantiza que el tráfico nunca se atasca.

El Giro de la Historia: ¡El Truco No Funciona!

El autor de este paper, Nikolay Ulyanov, dice: "Espera un momento. Probémoslo".

Usó la computadora para buscar configuraciones de puntos en ese globo terráqueo que fueran tan "rebelde" que no pudieran ser pintados con los números del -4 al 4.

La Analogía de la Fiesta:
Imagina que organizas una fiesta en una esfera gigante. Tienes reglas para los invitados:

• Si alguien entra por la puerta norte, su "gemelo" debe entrar por la puerta sur con el signo opuesto.
• Si tres amigos se sientan en una mesa redonda (un círculo grande), la suma de sus "números de suerte" debe ser cero.

Jain creía que siempre podrías asignar números del -4 al 4 para que todos se llevaran bien.
Ulyanov encontró dos fiestas (dos grupos de puntos) donde, sin importar cómo lo intentes, la regla se rompe. Para que la fiesta funcione, necesitas obligatoriamente usar los números -5 y 5.

Los Dos "Monstruos" Encontrados

El paper presenta dos ejemplos específicos (contraejemplos) que demuestran que la hipótesis de Jain es falsa:

1. El Expansor de 50 Puntos (El "Icosidodecaedro" inflado):

   • Imagina un poliedro (como un dado con muchas caras) que tiene 30 puntos.
   • Ulyanov tomó cada uno de esos puntos y lo "estiró" en un pequeño círculo, creando 50 puntos nuevos.
   • Cuando intentó asignar los números del -4 al 4, la computadora gritó: "¡IMPOSIBLE!". El sistema se bloqueó. Solo funcionaba si permitías usar el número 5.
   • Analogía: Es como intentar llenar un cubo de agua con vasos de 4 litros, pero el cubo requiere obligatoriamente un vaso de 5 litros para encajar perfectamente.

2. La Construcción de 36 Puntos (El "Cálculo de Raíces"):

   • Este es un grupo más pequeño y más astuto, creado usando matemáticas un poco más extrañas (raíces cuadradas y números dorados).
   • Tiene solo 36 puntos, pero es igual de rebelde.
   • Al igual que el primero, si intentas usar solo números hasta el 4, el rompecabezas no se cierra. Necesitas el 5.

¿Qué significa esto para el mundo?

1. La Hipótesis de Jain cae: Ya no podemos usar ese "truco del globo" para probar que todos los grafos tienen un flujo 5. La puerta se cerró por un lado.
2. El Misterio Persiste: La gran pregunta de si todos los grafos tienen un flujo 5 (la Conjetura de Tutte) sigue abierta. Ulyanov no dijo "no se puede", solo dijo "no se puede con este método específico".
3. El Futuro: El paper termina preguntándose: "¿Podemos encontrar un grupo de puntos que requiera el número 6? ¿O el 100?". Por ahora, el 5 es el límite máximo que han encontrado necesario.

En Resumen

Este paper es como un detective que llega a una escena del crimen (la teoría de Jain) y encuentra dos huellas dactilares que no coinciden con el sospechoso.

• Lo que pensábamos: "Si pintamos el globo con colores del -4 al 4, todo funcionará".
• La realidad: "Encontramos dos situaciones donde, si no usamos el color 5, el globo se rompe".

Es un trabajo fascinante que usa la potencia de las computadoras modernas (como un "juez" que prueba millones de combinaciones en segundos) para decirnos que la geometría es más complicada y sorprendente de lo que imaginábamos. ¡Y que a veces, para resolver un rompecabezas, necesitas una pieza que no estaba en la caja original!

Resumen técnico

A continuación presento un resumen técnico detallado del artículo "Graph Puzzles II.1: Counterexamples to Jain's second unit vector flows conjecture" (Rompecabezas de Grafos II.1: Contraejemplos a la segunda conjetura de flujos de vectores unitarios de Jain), escrito por Nikolay Ulyanov.

1. Planteamiento del Problema

El artículo aborda dos conjeturas propuestas por K. Jain relacionadas con los flujos de vectores unitarios en grafos, las cuales, de ser ciertas, implicarían la famosa Conjetura del Flujo 5 de Tutte (que todo grafo cúbico sin puentes admite un flujo no nulo 5).

• Conjetura 1 (Flujos de vectores unitarios): Todo grafo sin puentes admite un flujo $f: E(G) \to S^2$ (donde cada arista se asigna un vector unitario en $\mathbb{R}^3$).
• Conjetura 2 (Flujo $S^2$ no nulo 5): Existe una aplicación $q: S^2 \to \{-4, -3, -2, -1, 1, 2, 3, 4\}$ tal que:
  1. Los puntos antipodales suman 0 ($q(-x) = -q(x)$).
  2. Cualquier tripleta de puntos equidistantes en un círculo máximo suma 0.

El objetivo del paper es demostrar que la Conjetura 2 es falsa. Específicamente, se busca encontrar subconjuntos finitos de la esfera $S^2$ que no admitan una etiquetación con valores en $\{\pm 1, \dots, \pm 4\}$, forzando el uso de valores $\pm 5$ (lo que equivaldría a requerir un flujo no nulo 6 en lugar de uno 5).

2. Metodología

El autor emplea un enfoque combinado de geometría discreta, teoría de grafos y verificación computacional mediante lógica booleana (SAT).

1. Construcción Geométrica: Se diseñan configuraciones finitas de puntos en la esfera unitaria $S^2$. Estas configuraciones se basan en estructuras poliédricas conocidas (como el icosaedro truncado o icosidodecaedro) y nuevas construcciones algebraicas.
2. Definición de Restricciones: Para cada conjunto de puntos, se identifican las "tripletas" (tres puntos equidistantes en un círculo máximo) que deben sumar cero bajo la función $q$.
3. Codificación SAT: El problema de etiquetado se traduce en una instancia de Satisfacibilidad Booleana (SAT):
   • Se introducen variables booleanas para asignar valores en $\{-4, \dots, 4\}$ a cada punto antipodal.
   • Se imponen restricciones de "exactamente uno" (un punto tiene un solo valor).
   • Se imponen restricciones de antipodalidad ($q(-p) = -q(p)$).
   • Se imponen restricciones de suma nula para cada tripleta ($q(a) + q(b) + q(c) = 0$).
4. Verificación: Se utilizan solucionadores SAT (como PicoSAT/pycosat) para determinar si la fórmula resultante es satisfacible. Si es insatisfacible, se demuestra que no existe tal etiquetación con valores limitados a $\pm 4$.
5. Validación Formal: Además del SAT, el autor menciona la verificación formal utilizando el asistente de pruebas Lean 4 y el tactic bv_decide.

3. Contribuciones Clave y Resultados

El artículo presenta dos contraejemplos concretos que refutan la Conjetura 2:

Contraejemplo 1: Expansión de 50 puntos del Icosidodecaedro

• Construcción: Se parte de los 30 vértices del icosidodecaedro. Para cada vértice, se define un pequeño círculo en un plano específico. Luego, se intersectan los círculos correspondientes a pares de puntos originales que están a una distancia esférica de $2\pi/5$.
• Resultado: Se obtiene un conjunto de 50 puntos en $S^2$ con 40 tripletas de círculos máximos.
• Estructura Subyacente: Al considerar puntos antipodales como equivalentes, la estructura se relaciona con el Grafo de Petersen y una Escalera de Möbius de 10 vértices.
• Hallazgo: La instancia SAT generada (200 variables, 19,765 cláusulas) es insatisfacible. Esto prueba que no existe una asignación con valores en $\{\pm 1, \dots, \pm 4\}$. Sin embargo, sí existe una asignación válida usando valores $\{\pm 1, \dots, \pm 5\}$ (un flujo no nulo 6).

Contraejemplo 2: Construcción de 36 puntos basada en aritmética de raíces cuadradas

• Construcción: Se utiliza un conjunto de coordenadas generado mediante combinaciones lineales de raíces cuadradas de enteros ($\sqrt{1}, \sqrt{3}$). Se buscan tripletas $(c_1, c_2, c_3)$ que satisfagan $c_1^2 + c_2^2 + c_3^2 = 1$.
• Proceso de Filtrado: A partir de un componente conectado inicial de 126 puntos, se realiza un "poda" iterativa eliminando vértices que aparecen en pocas tripletas, convergiendo a un subconjunto mínimo.
• Resultado: Se obtiene un conjunto de 36 puntos con 13 tripletas.
• Hallazgo: La instancia SAT (144 variables, 6,710 cláusulas) es insatisfacible para el rango $\{\pm 1, \dots, \pm 4\}$. Al igual que en el primer caso, se confirma la existencia de una solución válida con valores hasta $\pm 5$.

4. Significado e Implicaciones

• Refutación de la Conjetura 2: El trabajo demuestra definitivamente que la Conjetura 2 de Jain es falsa. No existe una aplicación universal de $S^2$ a los enteros $\{\pm 1, \dots, \pm 4\}$ que satisfaga las condiciones de simetría y suma cero para todos los subconjuntos finitos posibles.
• Impacto en la Conjetura de Tutte: Dado que la Conjetura 2 era un paso necesario para probar la Conjetura del Flujo 5 de Tutte mediante el enfoque de flujos de vectores unitarios, este resultado indica que ese camino específico de demostración no es viable tal como se planteó originalmente.
• Nuevas Preguntas Abiertas:
  • ¿Es posible encontrar subconjuntos que requieran valores $\pm 6$ o superiores? (Hasta ahora, $\pm 5$ ha sido el límite máximo observado).
  • ¿Cuál es el subconjunto mínimo que sirve como contraejemplo?
  • ¿Se puede "rescatar" la conjetura restringiendo el dominio a subconjuntos infinitos con coordenadas algebraicas específicas que aún permitan un flujo 5? El autor sugiere que esto se explorará en un trabajo futuro.
• Observación sobre Flujos Modulares: El autor nota que, en sus experimentos, no hubo diferencia entre flujos no nulos $k$ y flujos no nulos módulo $k$, lo que sugiere una posible equivalencia que merece más estudio teórico.

En resumen, el artículo utiliza técnicas computacionales avanzadas para desmantelar una conjetura geométrica importante en la teoría de flujos de grafos, estableciendo límites inferiores más estrictos para la complejidad de las etiquetas necesarias en flujos vectoriales unitarios.