El matemático ruso refuta la hipótesis de 53 años sobre el colorido de las redes

El matemático ruso solo necesitó tres páginas para describir un método de colorear redes de cierto tipo que excediera las expectativas de los expertos.

Una hipótesis de 53 años sobre la mejor manera de asignar colores a los nodos de la red se refuta en un documento en línea. El trabajo en solo tres páginas muestra la existencia de métodos para colorear ciertos colores que han excedido todas las expectativas de los expertos.

Tareas para colorear redes [ ver número cromático / aprox. perev. ], inspirado por la cuestión de este color de mapas, en el que los países vecinos tienen diferentes colores, han estado en el centro de la investigación de los matemáticos durante casi 200 años. La tarea es comprender cómo colorear los nodos de una determinada red (o gráfico , cómo los llaman sus matemáticos) para que dos nodos conectados tengan colores diferentes. Dependiendo del contexto, este color puede proporcionar una forma efectiva de sentar a los invitados en una boda, organizar tareas de producción para intervalos de tiempo libres o incluso resolver sudoku .

Las tareas de colorear gráficos a menudo son fáciles de formular, pero increíblemente difíciles de resolver. Incluso en busca de una respuesta a la pregunta con la que comenzó todo este campo de investigación, ¿ son cuatro colores suficientes para colorear cualquier mapa ? - Tomó más de cien años (si está interesado, la respuesta es sí).

La tarea considerada en el nuevo trabajo, hasta ahora, no se consideraba una excepción. No se pudo resolver durante más de 50 años, y se refiere a productos tensoriales : gráficos compuestos de una combinación especial de dos gráficos diferentes (llamémoslos G y H). El producto tensor de los gráficos G y H es un gráfico nuevo y más grande, cada vértice del cual denota un par de vértices de los gráficos originales, uno de G y otro de H, mientras que dos vértices del producto tensor están conectados si ambos vértices correspondientes en G y sus vértices correspondientes en H.

Supongamos que eres un profesor de música y necesitas encontrar buenas parejas de duetos para un concierto de quinto año. Puedes hacer un gráfico, cuyos vértices serán estudiantes, y los enlaces entre los pares indicarán la presencia de buenas relaciones entre ellos. Luego puede hacer un segundo gráfico en el que cada nodo indique diferentes instrumentos musicales, y la conexión entre ellos es la presencia de partituras para un dúo de estos dos instrumentos. En el producto tensorial de estos dos gráficos, habrá un vértice para cada posible unión del alumno y el instrumento (por ejemplo, Alicia y el trombón), y los dos vértices se conectarán si dos alumnos trabajan bien juntos, y los dos instrumentos son compatibles.

En 1966, Stephen Hedetniemi , ahora profesor de la Universidad de Clemson en Carolina del Sur, sugirió en su disertación doctoral que el número mínimo de colores necesarios para colorear un producto tensor es el más pequeño de los dos colores necesarios para colorear cualquiera de los dos gráficos. . "Esta es una de las principales hipótesis en la teoría de gráficos", dijo Gil Kalai, de la Universidad Hebrea de Jerusalén. "Mucha gente trató de reflexionar sobre ella".

En las últimas décadas, los matemáticos han reunido una montaña de evidencia, algunos de los cuales hablaron sobre la verdad de la hipótesis, y otros, sobre su falsedad. Diferentes matemáticos tenían diferentes suposiciones sobre qué opción ganaría en última instancia. Pero todos estuvieron de acuerdo en que al menos era una tarea difícil.

"Personalmente, pensé que esta hipótesis era cierta, ya que una gran cantidad de personas inteligentes la estudiaron y tendrían que encontrar un contraejemplo", si eso existiera, dijo Anthony Bonato de la Universidad Ryerson en Toronto.

Y así, el matemático ruso Yaroslav Nikolaevich Shitov ideó una manera simple de crear contraejemplos, trabajos tensoriales que requieren menos colores que cualquiera de los dos gráficos que los componen. La evidencia salió "elemental pero brillante", dijo Pavol Hell de la Universidad Simon Fraser en Burnaby, Canadá.

Los gráficos de tensor están estrechamente relacionados con preguntas sobre mapeos de diferentes gráficos entre sí, y en esta área de las matemáticas, la hipótesis de Hedetniemi fue probablemente el mayor problema abierto, dijo Hell. "Este es un gran avance".

Hangouts coloridos

Para imaginar qué información puede extraerse de colorear el gráfico tensorial, imagine que va a invitar a sus amigos a su propiedad suburbana cada fin de semana. Y, como buen anfitrión, desea reunir personas que disfruten de la compañía del otro.

Usted sabe que algunos de sus amigos podrán hacer amigos rápidamente en función del trabajo, mientras que otros no. También sabe que sus amigos tienen un pasatiempo: otra forma a través de la cual los huéspedes pueden encontrar intereses comunes. Usted especula que un maestro de baile de violín puede pasar un buen rato hablando con un instructor de yoga jugando tenis o discutiendo música con un granjero que produce jarabe de arce y toca el piano, pero probablemente no sobre él de lo que hablará con un politólogo que colecciona sellos. Desea que cada par de invitados pueda encontrar algunos intereses comunes en cualquier fin de semana, ya sea un trabajo o un pasatiempo, y se pregunta cuántas reuniones debe organizar para ordenar a todos los invitados de la lista.


Yaroslav Shitov descubrió un contraejemplo de la hipótesis de Hedetniemi de 53 años a partir de la teoría de grafos

Podrías imaginar la relación de varios tipos de trabajo en forma de gráfico, cuyos nodos serán el trabajo, y cualesquiera dos trabajos estarán conectados por bordes, entre los cuales, lo más probable, no será posible encontrar temas comunes para la conversación (este enfoque puede parecer invertido, sin embargo, en el contexto de la coloración los gráficos tienen sentido, ya que usaremos colores para separar estos pares problemáticos). También podría hacer un gráfico, cuyos vértices sean pasatiempos diferentes e interconectar todos los incompatibles.

El producto tensorial de estos dos gráficos tendrá nodos para cada par de trabajo-afición, y los dos vértices se combinarán si ambos funcionan y ambos son incompatibles: esta es exactamente la situación que desea evitar el fin de semana. Si puede colorear los vértices del producto tensor para que los vértices conectados por las costillas tengan diferentes colores, esto le dará una forma de crear listas de invitados para diferentes fines de semana: puede invitar a personas correspondientes a vértices verdes al fin de semana "verde", vértices rojos al "rojo" ", Y así sucesivamente, y asegúrese de que haya invitados incompatibles en las listas los diferentes fines de semana. La cantidad de colores que use le indicará cuántos días de descanso tendrá que tomar en el calendario.

De este ejemplo se deduce que cualquier coloración válida del gráfico de trabajo puede transferirse al producto tensorial; simplemente puede colorear cada combinación de trabajo-afición en el mismo color que utilizó para el trabajo. Tal coloración conducirá al hecho de que en las reuniones cada pareja de invitados será compatible exclusivamente de acuerdo con sus intereses profesionales, independientemente de su pasatiempo.

Y viceversa, cualquier coloración admisible del gráfico de pasatiempo se transfiere al producto tensorial. Hedetniemi sugirió que la mejor manera de colorear un gráfico tensorial sería tener uno de los gráficos originales con un número mínimo de colores.

A primera vista, la hipótesis de Hedetniemi parece poco probable. Después de todo, si basa el color del tensor en el color del gráfico de trabajo, ignora todo lo que sabe sobre los pasatiempos compatibles de sus amigos y posiblemente comparte invitados que se llevan bien entre ellos. Si combina toda la información sobre el trabajo y los pasatiempos, puede usar menos flores y disfrutar de un merecido fin de semana sin invitados.

Y, sin embargo, durante más de 50 años, los matemáticos no pudieron encontrar un solo producto tensor, para colorear que requeriría menos colores que cualquiera de sus gráficos constituyentes. Pudieron demostrar que la hipótesis es cierta si no se necesitaban más de cuatro colores para colorear una de las dos gráficas. También es cierto en el caso más general de coloraciones "fraccionarias", cuando a cada vértice se le puede asignar una combinación de colores, por ejemplo, 2/3 de amarillo y 1/3 de verde. (En términos de reuniones de fin de semana, esto puede corresponder a una situación en la que hay tres periodistas en su lista de amigos, uno de los cuales juega tenis y usted invitó a dos de ellos al fin de semana "amarillo", y el tercero al "verde").

Estos hallazgos sugirieron que la hipótesis podría ser cierta, pero otros dijeron lo contrario. Por ejemplo, los matemáticos han demostrado que la hipótesis de Hedetniemi se desmorona para gráficos que requieren un número infinito de colores para colorear, o para gráficos dirigidos cuyos bordes tienen direcciones preferidas. Pero, a pesar del hecho de que los matemáticos probaron la hipótesis de Hedetniemi para algunos casos y la refutaron para otros, no pudieron resolver el problema en el campo que el mismo Hedetniemi consideró originalmente: gráficos finitos no dirigidos con coloración entera.

"En general, todos pensaron que era verdad, pero fue difícil probarlo o refutarlo", dijo Noga Elon de la Universidad de Princeton.

Dibujos para colorear

Shitov aplastó todas estas incertidumbres con una demostración clara y simple de la falsedad de la hipótesis de Hedetniemi. En el trabajo, cuya prueba principal se ajusta a una página, llena de matemáticas, muestra cómo crear un tipo especial de producto tensor, que requiere menos colores para pintar que para cualquiera de sus componentes.

Shitov comienza su trabajo observando lo que sucederá si combinamos el gráfico G con uno de sus gráficos exponenciales y obtenemos su producto tensorial. El gráfico exponencial tiene un nodo para cada uno de los colores posibles G con un cierto número fijo de colores (se permiten todos los colores posibles, no solo aquellos cuyos vértices conectados tienen colores diferentes). Si el gráfico G, por ejemplo, tiene 7 vértices, y hay 5 colores en nuestra paleta, entonces el gráfico exponencial tendrá 5 ⁷ vértices, por lo que se llama exponencial.


La hipótesis de Stephen Hedetniemi del número mínimo de colores para colorear el producto tensor de gráficos no ha sido confirmada durante más de 50 años.

Si volvemos a la opción de colorear, en la cual los vértices conectados deben ser de diferentes colores, entonces no podemos garantizar que los cinco colores de nuestra paleta sean suficientes para colorear el gráfico G, y de la misma manera podrían no ser suficientes para colorear el gráfico exponencial con 5 ⁷ vértices . Sin embargo, los matemáticos saben desde hace mucho tiempo que hay un gráfico para el cual cinco colores son suficientes: es un producto tensor que consiste en G y su gráfico exponencial.

De hecho, todos los gráficos exponenciales tienen esta propiedad: un producto tensorial que combina un gráfico exponencial con el gráfico a partir del cual se creó puede colorearse con exactamente el mismo número de colores que el gráfico original. Shitov refutó la hipótesis de Hedetniemi, mostrando cómo es posible crear un gráfico G que requiera más colores para colorearlo y su gráfico exponencial.

Hedetniemi declaró que estaba "completamente encantado" con la resolución de la situación con su hipótesis después de tantas décadas. La evidencia de Shitov "tiene una cierta elegancia, simplicidad y calidad", escribió en un correo electrónico.

El nuevo contraejemplo resultó ser astuto e inventivo, dicen los matemáticos, y no necesita herramientas matemáticas avanzadas complejas. "Para un especialista en teoría de grafos, este diseño puede explicarse en dos oraciones", dijo Kalai.

Por qué nadie ha notado este argumento durante más de 50 años es un misterio para los matemáticos. "A veces una pequeña gema se esconde debajo de una pila de follaje", dijo Hell. "Shitov simplemente logró entender esta pregunta más profundamente que todos los demás".

Los gráficos de Shitov resultan ser gigantescos: no calculó su tamaño exacto, pero estima que el gráfico G probablemente tendrá aproximadamente ^4,100 vértices, y los gráficos exponenciales tendrán al menos ^4,000 vértices, es decir, mucho más que el número aproximado de partículas elementales en universo observable [ aproximadamente 10 ⁸⁰ / aprox. perev. ]

Pero, por supuesto, todo depende del observador. Shitov cree que su contraejemplo "no es tan grande". En matemáticas, puedes encontrar contraejemplos, en comparación con los cuales serán muy pequeños ".

Y aunque es poco probable que pueda invitar a ^4.000 a su casa de campo, el trabajo de Shitov no rechaza la existencia de contraejemplos de un tamaño mucho más pequeño. Pero ahora que los matemáticos saben que la hipótesis de Hedetniemi es falsa, la pregunta natural será cómo es exactamente falsa: ¿cómo se pueden necesitar menos colores para colorear un producto tensor en comparación con sus gráficos constituyentes, y cuál es el número mínimo de nodos y bordes que pueden tener esos contraejemplos?

Mientras tanto, Elon dijo que el nuevo trabajo contiene una importante lección para todos los matemáticos: "A veces, la razón por la cual una hipótesis es tan difícil de probar es que es falsa".