Casi coincidiendo con su 30 cumpleaños (fue el pasado 3 de junio), el nombre de Yaroslav Shitov ha aparecido en buena parte de la prensa mundial. Este matemático ruso ha probado que una conjetura con más de medio siglo de vida sobre un problema de teoría de grafos es falsa, dando un contraejemplo, es decir, aportando un caso en el que no se cumple lo que la conjetura predecía que sucedía siempre.

Los grafos son una de las estructuras más simples y, a la vez, más versátiles de las matemáticas, con gran cantidad de aplicaciones (desde el diseño de redes de comunicaciones a la distribución de mercancías y planificación de la producción). Los componen dos tipos de elementos: vértices o puntos, y aristas, que son parejas de puntos. Se suele representar un grafo por un dibujo en el que los vértices son puntos en el plano y las aristas son segmentos que los unen.

Uno de los problemas más estudiados en este campo trata de encontrar el mínimo número de colores que se pueden asignar a los vértices de tal forma que no existan dos con el mismo color que estén unidos por una arista.

El problema de coloreado de grafos se suele usar para clasificar objetos o para optimizar procesos. Por ejemplo, los vértices pueden ser tareas a completar por un conjunto de trabajadores y una arista entre dos vértices indica que esas dos tareas las ha de realizar el mismo trabajador, o que son incompatibles por alguna otra razón. Si cada color representa una franja de tiempo, podemos asegurar que las tareas representadas en el grafo anterior necesitan al menos tres franjas de tiempo para completarse.

La historia del coloreado de grafos es muy extensa y se puede remontar a mediados del siglo XIX, cuando Francis Guthrie (o su hermano) conjeturó que cualquier grafo que se pueda dibujar en el plano de forma que dos aristas distintas no se crucen, salvo en un vértice común, se puede colorear siempre con cuatro colores o menos. Este es el llamado problema del mapa de los cuatro colores, que fue resuelto definitivamente por los matemáticos Kenneth Appel y Wolfgang Hanken en 1976, más de 125 años después.

Aunque parezcan juegos de niños, los problemas de coloración pueden ser endiabladamente complicados: determinar si un grafo puede ser coloreado con menos de una cantidad fija de colores es un problema NP-completo. Esto significa que si nos dan una posible coloración, podemos comprobar tanto si tiene menos de los colores que nos piden y si es válida, pero es tremendamente difícil encontrar esa coloración si no nos la dan. Por tanto, si encontramos un algoritmo que resuelva de forma eficiente el problema de colorear grafos (con una cantidad de operaciones menor que una cantidad relacionada con el número de vértices del grafo), podemos ir al instituto Clay y reclamar un millón de dólares, porque habremos demostrado que P es distinto a NP, y con ello uno de los célebres problemas del milenio cuya resolución lleva asignada ese premio. Si alguno de los lectores tiene el algoritmo pero no entiende por qué implica que P es distinto de NP, los autores de este artículo se brindan a aclarar las dudas. Compartiendo parte del premio, claro está.

Dada la complicación de los problemas de coloreado, un avance sería saber cuál es el mínimo número de colores necesarios para algunos tipos de grafos. Y en este contexto aparece la conjetura de Hedetniemi. En 1966 Stephen Hedetniemi conjeturó en su tesis doctoral que dados dos grafos G y H, el número de colores necesario para colorear el grafo producto tensorial GXH es el menor de los colores necesarios para colorear G y H. Este grafo se obtiene combinando de cierta forma los vértices y aristas de G y H.

Esto se cumplía para todos los ejemplos que se habían encontrado hasta hace un mes, pero nadie había conseguido demostrarlo formalmente. Y por una buena razón: porque es falso. El joven matemático ruso Shitov ha encontrado dos grafos G y H tales que su producto tensorial necesita menos colores que los requeridos para colorear tanto G como H, demostrando así que la conjetura de Hedetniemi es falsa.

Los ejemplos G y H de Shitov son grafos enormes: es posible que G tenga 2200 vértices, lo cual es un número inmenso, de un orden de magnitud cercano al número de partículas elementales que podemos encontrar en todo el universo visible. Pero H es aún mayor, mucho mayor, con más de 220000 vértices. De hecho no los construye explícitamente en su corto artículo (dos páginas y media). Pero demuestra que existen basándose en propiedades conocidas, con lo que queda resuelto el problema.

Fuente: elpais.com