En 2004, dos matemáticos idearon un plan para un sándwich que no estaba hecho de pan y queso. Estaba hecho de grafos. Querían entender un tipo de grafo —uno que aparece en todas partes en matemáticas y ciencias de la computación, pero que es difícil de estudiar— colocándolo entre dos grafos más simples. Si el sándwich funcionaba, el grafo del medio heredaría todo tipo de cualidades útiles de los grafos externos. La idea era simple. La ejecución tomó veinte años.
¿Qué es un grafo?
Un grafo es una colección de puntos, llamados vértices, unidos por líneas, llamadas aristas. Esas aristas pueden representar casi cualquier cosa: amistades, páginas web enlazadas entre sí, neuronas que se activan en el cerebro. Los matemáticos han pasado generaciones estudiando cómo se comportan estas conexiones, y un tipo particular de grafo —el grafo regular— siempre ha sido un problema. Sus aristas forman patrones estrechos e interdependientes que resisten el análisis fácil.
Grafos binomiales aleatorios
El tipo de grafo más fácil proviene de un modelo desarrollado a finales de la década de 1950 por Edgar Gilbert en Bell Labs. Estaba estudiando redes telefónicas e inventó una manera simple de construir un grafo «aleatorio». Comience con un conjunto de vértices. Elija cualquier par de ellos. Lance una moneda. Cara significa que se dibuja una arista entre ellos; sello significa que se pasa al siguiente. Repita hasta que se haya considerado cada par.
Este modelo se conoció como el grafo binomial aleatorio. Era relativamente fácil de analizar, y para la década de 1970, los matemáticos habían descubierto exactamente cuándo uno de estos grafos contendría un ciclo hamiltoniano —un camino que toca cada vértice exactamente una vez. Ese fue un descubrimiento interesante.
Los grafos regulares son más difíciles
Luego vinieron los grafos regulares. Estos son grafos donde cada vértice tiene el mismo número de aristas. A menudo son más precisos para modelar redes del mundo real que los grafos binomiales, pero son mucho más difíciles de estudiar. Pasaron 20 años después del resultado del ciclo hamiltoniano para los grafos binomiales antes de que alguien pudiera probar lo mismo para los grafos regulares.
La dificultad proviene de la interdependencia de las aristas. En un grafo regular, agregar o eliminar una arista en un lugar afecta la estructura del grafo en otro lugar. Eso los hace un fastidio para trabajar.
La idea de Kim y Vu
Jeong Han Kim, entonces en Microsoft Research, y Van Ha Vu, entonces en la Universidad de California, San Diego, tenían un plan. Querían aproximar grafos regulares con grafos binomiales. Si eso fuera posible, las cualidades difíciles de demostrar de un grafo regular podrían venir gratis, heredadas del grafo más simple. Su idea era construir un sándwich —un grafo binomial abajo, un grafo regular en el medio y otro grafo binomial arriba— y demostrar que el grafo del medio tenía que coincidir con los exteriores de ciertas maneras.
La analogía es literal: los grafos binomiales son el pan, el grafo regular es el queso, y la receta tiene que apilarlos de modo que el queso siempre encaje entre las rebanadas. Ese es el punto central. Demuestra algo sobre el pan y sabrás que el queso lleva la misma propiedad.
Cómo se mantienen unidas las capas
El sándwich tiene dos mitades. La mitad inferior pide una receta que te dé un grafo regular que contenga un grafo binomial. Las aristas del grafo binomial son un subconjunto de las aristas del grafo regular. Si el grafo binomial gana una cualidad al agregar aristas, el grafo regular la hereda. La mitad superior pide una receta que te dé un grafo regular contenido dentro de un grafo binomial. Si el grafo binomial pierde una cualidad al eliminar aristas, el grafo regular también la pierde.
Kim y Vu conjeturaron que, siempre que el grafo regular tenga un número razonable de aristas, casi siempre se puede construir este sándwich. Es una afirmación audaz. El desafío es que los dos grafos exteriores generalmente se construyen usando procesos aleatorios completamente diferentes, y la receta tiene que funcionar para ambos a la vez.
Llega la demostración
A lo largo de los años, los matemáticos demostraron la mitad inferior del sándwich de Kim y Vu. También demostraron la mitad superior en algunos entornos. Pero el sándwich no estaba completo. La demostración completa requería una manera de conectar el pan y el queso de cualquier sándwich, construyendo las capas en tándem para que siempre encajaran.
En 2025, tres matemáticos encontraron una manera de llevar las técnicas de su campo hasta sus límites y completaron la búsqueda. La demostración de la conjetura estaba completa.
Por qué importa el sándwich
La importancia no es solo teórica. El sándwich conecta dos procesos aleatorios muy diferentes que los matemáticos estudian. Muestra que esos procesos están conectados de una manera más profunda y más elegante de lo que nadie había imaginado. El resultado es un puente entre dos mundos de la teoría de grafos, y abre puertas para investigaciones futuras.
Pu Gao, una matemática de la Universidad de Waterloo que ha trabajado en el problema, lo expresó con claridad: «La noción es tan bella». Añadió: «Lo que más me atrae es, en realidad, su belleza».
Michael Krivelevich, un matemático de la Universidad de Tel Aviv que también ha trabajado en el problema, describió el avance como una secuencia de ideas que se construyen unas sobre otras. Cada paso, dijo, «requiere una muy buena técnica. Requiere ingenio».
El largo camino hacia la culminación
El camino desde la conjetura hasta la demostración fue largo. Esta es la forma aproximada de ese camino:
- 2004: Kim y Vu formulan la conjetura del sándwich.
- Fines de la década de 1950: Gilbert inventa el modelo de grafo binomial aleatorio; Erdős y Rényi desarrollan un modelo similar de manera independiente.
- Década de 1970: Los matemáticos demuestran cuándo los grafos binomiales contienen ciclos hamiltonianos.
- Después de la década de 1970: Los matemáticos resuelven el problema equivalente para grafos regulares, 20 años después del resultado binomial.
- 2025: Tres matemáticos completan la demostración de la conjetura del sándwich.
Los hechos clave son simples de enunciar:
- Conjetura formulada: 2004
- Modelo de grafo binomial: finales de la década de 1950 (Gilbert); modelo similar de Erdős y Rényi
- Ciclo hamiltoniano demostrado para grafos binomiales: década de 1970
- Ciclo hamiltoniano demostrado para grafos regulares: 20 años después del resultado binomial
- Demostración completada: 2025
Lo que viene después
El sándwich es ahora una herramienta. Probablemente se utilizará para demostrar nuevas propiedades de los grafos regulares, y puede conducir a nuevas conexiones entre diferentes modelos de redes aleatorias. La belleza de la idea, como señaló Gao, es que alinea dos mundos muy diferentes.
La demostración es un hito. Demuestra que dos procesos aleatorios están conectados de una manera más profunda de lo esperado, y abre una puerta a lo que viene después. Para los matemáticos, el sándwich es un recordatorio de que a veces la mejor manera de entender algo es ponerlo entre dos cosas que ya se conocen.
El camino de 2004 a 2025 implicó décadas de progreso incremental, cada paso construido sobre el anterior. El avance final provino de tres matemáticos que llevaron las técnicas existentes hasta sus límites. El resultado es un puente entre dos mundos de la teoría de grafos, y abre puertas para futuras investigaciones.
Material de origen: “Mathematicians Build Long-Awaited Graph Sandwich,” Quanta Magazine.
Recibe El Cuaderno.
Las mejores historias del día y cada veredicto nuevo, en español claro, en tu correo a las siete. Un correo al día, nada más.