En el otoño En 1972, Vance Faber fue el nuevo profesor de la Universidad de Colorado. Cuando dos matemáticos influyentes, Paul Erdős y László Lovász, vinieron de visita, Faber decidió organizar una fiesta de té. Erdős en particular tenía una reputación internacional como investigador excéntrico y enérgico, y los colegas de Faber estaban ansiosos por conocerlo.

«Mientras estábamos allí, como en muchas de estas fiestas de té, Erdős estaba sentado en un rincón rodeado de sus fans», dijo Faber. «Tenía discusiones sobre diferentes cosas al mismo tiempo, a menudo en varios idiomas».

Erdős, Faber y Lovász centraron su conversación en los hipergráficos, una nueva idea prometedora en la teoría de grafos en ese momento. Después de algún debate, llegaron a una sola pregunta, que más tarde se conoció como la conjetura de Erdős-Faber-Lovász. Es el número mínimo de colores necesarios para colorear los bordes de los hipergráficos dentro de ciertas restricciones.

«Fue lo más fácil que se nos ocurrió», dijo Faber, ahora matemático del Centro de Ciencias de la Computación del Instituto de Análisis de Defensa. “Trabajamos un poco en eso durante la fiesta y dijimos: ‘Bueno, terminaremos esto mañana. ‘Eso nunca sucedió. «

El problema resultó ser mucho más difícil de lo esperado. Erdős a menudo lo anunciaba como una de sus tres conjeturas favoritas y ofrecía una recompensa por la solución, que aumentó a 500 dólares cuando los matemáticos se dieron cuenta de la dificultad. El problema era bien conocido en los círculos de la teoría de grafos y dio lugar a muchos intentos de solución, ninguno de los cuales tuvo éxito.

Pero ahora, casi 50 años después, un equipo de cinco matemáticos finalmente ha demostrado que la fiesta del té es cierta. Una preimpresión lanzada en enero limita la cantidad de colores que podrían ser necesarios para sombrear los bordes de ciertos hipergráficos para que ningún borde superpuesto sea del mismo color. Demuestran que el número de colores nunca es mayor que el número de vértices en el hipergráfico.

El enfoque consiste en apartar con cuidado algunos bordes de un gráfico y colorear otros al azar. Se trata de una combinación de ideas que los investigadores han utilizado durante los últimos años para resolver una serie de problemas abiertos de larga data. No estaba disponible para Erdős, Faber y Lovász cuando se les ocurrió el problema. Ahora, los dos matemáticos supervivientes del trío original pueden esperar las innovaciones matemáticas que despertaron su curiosidad.

«Es un buen trabajo», dijo Lovász de la Universidad Eötvös Loránd. «Estoy muy satisfecho con este progreso».

Suficientes colores

Cuando Erdős, Faber y Lovász estaban tomando té y haciendo matemáticas, tenían una nueva estructura gráfica en sus cabezas. Los gráficos ordinarios están formados por puntos llamados vértices y conectados por líneas llamadas aristas. Cada borde conecta exactamente dos puntos de esquina. Los hipergráficos observados Erdős, Faber y Lovász son, sin embargo, menos restrictivos: sus aristas pueden corregir cualquier número de vértices.

Esta noción más amplia de un borde hace que los hipergráficos sean más versátiles que sus primos de cubo y radio. Los diagramas estándar solo pueden expresar relaciones entre pares de cosas, p. Ej. B. dos amigos en una red social (cada persona representada por un vértice). Sin embargo, para expresar una relación entre más de dos personas, como la pertenencia conjunta a un grupo, cada borde debe contener más de dos personas, lo que permiten los hipergráficos.

Sin embargo, esta versatilidad tiene un precio: es más difícil probar las propiedades universales de los hipergráficos que de los gráficos ordinarios.

“Muchos de los milagros [of graph theory] O desaparece o las cosas se ponen mucho más difíciles cuando se cambia a hipergráficos ”, dijo Gil Kalai de IDC Herzliya y la Universidad Hebrea de Jerusalén.

Por ejemplo, los problemas de coloración de los bordes se vuelven más difíciles con los hipergráficos. En estos escenarios, el objetivo es colorear todos los bordes de un gráfico (o hipergráfico) para que no haya dos bordes que se encuentren en un vértice del mismo color. El número mínimo de colores requerido para esto se llama índice cromático del diagrama.

La conjetura de Erdős-Faber-Lovász es una cuestión de color sobre cierto tipo de hipergráfico en el que los bordes se superponen mínimamente. En estas estructuras, conocidas como hipergráficos lineales, no se permite que dos bordes se superpongan en más de un vértice. La conjetura predice que el índice cromático de un hipergráfico lineal nunca es mayor que su número de vértices. En otras palabras, si un hipergráfico lineal tiene nueve vértices, sus bordes no se pueden colorear con más de nueve colores, independientemente de cómo los dibuje.