Entusiasmo por el polinomio cromático

Los matemáticos somos gente dada al entusiasmo. Quizá no se nos vea por las facultades o las empresas gritando como energúmenos, dando saltos o abrazando al primero que nos encontramos, pero esto es porque nuestro entusiasmo no necesita en general de expansiones públicas ni juerga vocinglera. Es un entusiasmo íntimo. Sea cuando consigues resolver el problema que te preocupaba durante meses, cuando reconoces la genialidad de una idea, o cuando captas la belleza oculta y, sin embargo, indiscutible de un razonamiento, un fuego que no admite confusión te llena el corazón, tu cuerpo entero sonríe —aunque a veces no lo exteriorice más que en un leve gesto— y una oleada ardiente te invade y te recuerda que en esos momentos, sin duda alguna, estás vivo y la vida merece ser vivida. Casi arriesgaría que estos clímax instantáneos se hallan presentes en el fondo de la vocación de cualquier matemático.

Hace unos días, preparando una clase, volvió a mí durante unos segundos la maravillosa sensación. Aparecida ante mí como si la viera por primera vez, relumbró en mi mente la imagen poderosa del polinomio cromático, y de un golpe, como una epifanía, contemplé la dosis inmensa de genialidad que debió ser necesaria para concebir tal concepto, que supone un puente entre la geometría y el álgebra —o lo que es lo mismo, entre el dibujo y el número— de una elegancia, economía y precisión casi incomparables. Tras recuperarme un poco reparé en que cualquiera puede entender las ideas necesarias para captar la esencia del asunto dedicándole solo un rato de lectura más o menos atenta; y así, convencido de esto, consideré poco menos que un deber escribir este artículo, en la esperanza inicial de transmitir una sensación parecida a la mía, y en la más ambiciosa de que gente que ve las mates como algo ajeno a su vida pueda, por un momento, sumergirse en ellas y disfrutar.

Antes de llegar a las maravillas del polinomio cromático, primero tendremos que hablar un poquito de grafos. Seguramente, los grafos están entre los objetos matemáticos más importantes que uno pueda citar, y a diferencia de otros, se entiende lo que es un grafo al primer golpe de vista. Aquí tenemos un par de ejemplos:

Vistos y aprehendidos los dibujos, entender una definición un poco más formal resulta sencillo. Un grafo será un conjunto de vértices V y otro de aristas A, tales que cada arista de A tiene como extremos dos vértices distintos de V. En ocasiones, se permite que haya aristas cuyos vértices inicial y final sean el mismo (grafos con lazos) o que dos aristas puedan compartir los mismos vértices inicial y final (multigrafos). Sin embargo, en este artículo solo hablaremos de grafos simples, en los que no se permite ninguna de las dos veleidades anteriores. Además, asumiremos que el número de vértices (y por lo tanto el de aristas) es finito.

Hay que decir que cualquier avance importante que se consigue en teoría de grafos repercute inmediatamente en multitud de campos, porque los grafos permean casi todas las ramas de conocimiento en las que se desarrollan actualmente las ciencias y la ingeniería: las redes sociales son grafos, cualquier fenómeno de difusión (líquidos, epidemia, fenómenos migratorios) tiene un grafo detrás, las redes eléctricas son grafos, los circuitos se representan mediante grafos, las redes de tuberías, las relaciones personales, las carreteras… Casi todo es susceptible de ser modelado por un grafo. Es un modelo casi universal.

Centrando el foco un poco más, es casi seguro que algún lector avisado se habrá dado cuenta ya de que, si vamos a hablar de un objeto que se llama polinomio cromático, por algún lado tienen que aparecer colores. Y tendrá razón: el polinomio cromático surge a partir del problema de la coloración de grafos, cuyas consecuencias en muchas disciplinas son también innumerables —hoy mismo acabo de encontrarme un problema de coloración para asignar frecuencias a compañías de móviles—, y que vamos a enunciar inmediatamente antes de seguir adelante:

EL PROBLEMA DE LA COLORACIÓN: Dado un grafo G y una paleta de colores {rojo, azul, amarillo…}, decidir si se pueden colorear los vértices de manera que dos vértices que compartan una arista no lleven el mismo color.

Ahora tocaría una interesantísima disgresión sobre el origen de este problema (la coloración de mapas), el teorema de los cinco colores, el número cromático, el teorema de los cuatro colores, y cómo una gran parte de la comunidad matemática se tiró de los pelos con la demostración de este último, que puede considerarse algo así como el equivalente matemático del urinario de Duchamp. Sin embargo, vamos a obviar dicha explicación, porque todas estas cuestiones ya han sido perfectamente tratadas en dos artículos cuya lectura recomiendo con fervor, y que además de estar fantásticamente escritos por la gran Clara Grima, complementan a este. O, por mejor decir, este los complementa a aquellos: «Los colores de la radio», en esta misma revista, y «Por qué solo cuatro colores», en Naukas.

El problema que da origen al polinomio cromático parece una vuelta de tuerca al anterior, pero en realidad es bastante diferente:

CONTANDO COLORACIONES: Dado un grafo G y una paleta con un número determinado k de colores, determinar de cuántas maneras diferentes se puede colorear el grafo G con colores de esa paleta, sujetas de nuevo las coloraciones a la restricción de que dos extremos de una arista deben llevar colores diferentes.

Aquí hay que aclarar qué significa «diferentes», aunque la idea corresponde completamente con la intuición: dos coloraciones de un grafo llevadas a cabo con la misma paleta se consideran diferentes si al menos uno de los vértices del grafo tiene color diferente en cada una de las dos.

Así pues, lo primero que hay que hacer es modelar este problema de un modo apropiado. Para empezar, nos damos cuenta de que dada una paleta de colores cualquiera, desde el punto de vista de contar coloraciones nos importa poco cuáles sean los colores concretos de la paleta; en realidad, solo nos va a importar el número k de colores que esta contenga. Dicho de otro modo, si un grafo podemos colorearlo exactamente de diez maneras diferentes con los colores rojo, amarillo y azul, igual podremos colorearlo de diez maneras diferentes con los colores verde, naranja y rosa, o viceversa. Solo nos va a importar en cada caso el número de colores de la paleta, no los colores concretos.

Ahora podemos definir una asignación (lo que en matemáticas se llama una función) del siguiente modo: para cada paleta con k colores y para cada grafo G, P_G(k) será el número de coloraciones posibles del grafo G con colores de la paleta. A esta asignación es a lo que se llama polinomio cromático de G.

Por fin, después de un montón de párrafos, ha aparecido el objeto del título. Antes de seguir adelante, merece la pena dedicarle unas líneas al primer tipo al que se le ocurrió esta idea, y que resultó ser una de las mentes más brillantes de su generación. Se dice que Poincaré y Hilbert fueron los últimos matemáticos que consiguieron tener una visión completamente global de su ciencia, y que a partir de ellos (principios del siglo XX) todo se hizo tan específico que tal cosa se volvió imposible para una sola persona. Puede ser cierto, pero si alguien anduvo cerca después de ellos fue George David Birkhoff. De origen holandés y considerado más tarde el mejor matemático americano de su época, el joven George comenzó por leerse las obras completas de Poincaré, que en un contexto intelectual es algo así como hacerse un ironman diario tres veces al día durante un año. Con veintiocho añitos lo ficharon en Harvard y se convirtió en el gran gurú de una de las universidades más prestigiosas del mundo. Era un tipo duro, seco, exigente y con una capacidad de trabajo virtualmente ilimitada. Además de poner las bases para resolver el problema de los cuatro colores —que es por lo que aparece aquí ahora—, el amigo dejó el teorema ergódico, investigaciones sobre la relatividad, una prueba del último teorema geométrico de Poincaré y una nueva axiomatización de la geometría. Cuando murió había firmado más de doscientos artículos de investigación —la mayor parte en solitario— y cinco libros. Hablando en plata, una bestia.

Como íbamos diciendo, Birkhoff fue el primero a quien se le ocurrió esa asignación, y seguramente el mismo lector avisado del que hablábamos antes estará escamado con que a esta función se la llame «polinomio». Recordemos, por si alguien tiene las matemáticas básicas en un rincón perdido de su mente, que un polinomio (en una variable) puede verse como una expresión a_nxⁿ +a_n-1x^n-1+…+a₀, donde los a_n son constantes y x es una variable. Por ejemplo, 3x²+4x+5 o 4x⁷+x son polinomios. Los polinomios también se interpretan como asignaciones: para cada valor de x ejecutamos las operaciones correspondientes y obtenemos el valor del polinomio en x. Así, en el primer ejemplo, si tomamos x=3, obtenemos que el valor del polinomio en 3 es 44.

Cuando uno lee la definición de polinomio cromático, en principio, no aparece un polinomio por ningún sitio, solo una asignación cualquiera. Este es precisamente el primer motivo de entusiasmo que al arriba firmante le provoca el polinomio cromático: ¡que efectivamente es un polinomio! Antes de razonar por qué ocurre esto, vamos a ver un ejemplo de polinomio cromático sencillo, que nos va a venir de perilla para nuestro razonamiento.

Consideremos el grafo que tiene n vértices y ninguna arista. Dada una paleta con k colores, ¿de cuántas maneras podemos colorearlo? Para el primer vértice, podemos asignar k colores, pero para el segundo también, y para el tercero, y para el cuarto, porque no hay ninguna restricción (no hay aristas). Por tanto, el polinomio cromático de este grafo será exactamente kⁿ, que es claramente un polinomio en k. El lector puede hacer la prueba, por ejemplo, con tres vértices y dos colores, para obtener exactamente ocho coloraciones diferentes.

El gran truco para construir el polinomio cromático, y a la vez para que aparezcan sus maravillas, es el algoritmo de eliminación-contracción, que es un método para expresar el polinomio cromático de un grafo de r aristas como diferencia de los polinomios cromáticos de dos grafos tales que cada uno tiene, como mucho, r-1 aristas. Veamos cómo funciona.

Tomamos un grafo G con r aristas, y una paleta de k colores de manera que sea posible colorear G con esos k colores. Nos fijamos en una arista, que llamamos a, y construimos dos grafos nuevos:

• El grafo diferencia G–a es un grafo que tiene los mismos vértices que G y las mismas aristas que G excepto la arista a, que la borramos (los extremos los dejamos).

• El grafo cociente G_a es un grafo en el cual identificamos los dos vértices de a en uno solo. Por tanto, G_a tiene un vértice menos que G, la arista G_a ha desaparecido, dos aristas no incidentes que tengan como extremos los vértices de a pasan a tener un vértice común, y dos aristas cualquiera que formen un triángulo con a en G pasan a ser la misma arista en G_a. Se realiza, de hecho, un «pegado» en el grafo.

Aquí tenemos un ejemplo de estas construcciones para un grafo sencillo:

Pensemos ahora en una coloración de G–a. Pueden pasar dos cosas: que los extremos de la arista que hemos quitado lleven el mismo color, o colores diferentes. En el primer caso, la coloración da una coloración de G_a (con el vértice distinguido de G_a con el color de los extremos de la arista que hemos quitado en G), y en el segundo, la coloración de G-a da una coloración de G. Dicho de otro modo, habrá tantas coloraciones de G–a con k colores como coloraciones de G_a con k colores más coloraciones de G con k colores. Escrito resumidamente (!y en esta expresión está todo!):

P_G(k) = P_G-a(k) – P_Ga(k).

Lo que hemos conseguido aquí es expresar el polinomio cromático de G en función de los polinomios cromáticos de grafos con al menos una arista menos. Ahora, si reiteradamente vamos quitando aristas de esta manera de G–a y G_a, acabaremos escribendo P_G(k) como sumas y restas de polinomios cromáticos de grafos vacíos. Como sabemos que estos últimos son polinomios de verdad, de pura cepa, P_G(k) también lo será.

De este modo, además de ver que P_G(k) es un polinomio, hemos encontrado un método para construirlo, que no solo puede comprender cualquier persona, sino lo que es más importante desde el punto de vista del cálculo, que entiende cualquier ordenador. Así, el polinomio cromático puede calcularse, dado un grafo, de modo completamente automático (otra cosa es el tiempo que se tarde).

Hemos visto que todo grafo da lugar a un polinomio cromático. ¿Será cierto también que dado un polinomio cualquiera podemos construir un grafo que lo tenga como polinomio cromático? En este caso, la respuesta es no, porque hay ciertas restricciones que un polinomio cromático debe cumplir siempre:

• El término independiente a₀ del polinomio cromático es siempre cero.
• Todos los coeficientes del polinomio cromático son distintos de cero a partir de un cierto a_j.
• Todos los coeficientes del polinomio cromático son números enteros.
• Los coeficientes del polinomio cromático se van alternando en signo.

Animamos al lector a reflexionar por qué los tres primeros hechos son ciertos (el cuarto tiene algo más de miga). Una pista: para los dos primeros, ver qué pasa si intentamos colorear un grafo con cero colores o con un color; y para el tercero, echarle un vistazo a cómo acaba el algoritmo de arriba.

Solo el hecho de averiguar que el polinomio cromático es un polinomio ya sería motivo suficiente para sacar a hombros a Birkhoff por las puertas de Harvard. Sin embargo, lo más increíble del polinomio cromático es la enorme información que contiene sobre el grafo, codificada en su grado y sus coeficientes. Ahí van algunas perlas:

• El grado del polinomio cromático es siempre el número de vértices del grafo.
• Si el polinomio cromático es de grado n, el coeficiente de grado n-1 cambiado de signo es el número de aristas del grafo.
• Si el polinomio cromático es de grado n, el coeficiente de grado n-2 (ligeramente retocado) cuenta el número de triangulitos que se forman en el grafo.
• Dado un grafo G, una componente de G está formada por todos los vértices tales que existe un camino dentro de G entre ellos, y las aristas de G que los unen. Entonces, si el primer término no nulo del polinomio cromático es de grado j, el grafo tiene j componentes.

Todas estas propiedades, que a primera vista parecen magia potagia, son en realidad fáciles de probar, y muestran que ya a primera vista el polinomio cromático codifica una gran parte de la estructura del grafo. Otras propiedades que no vamos a describir aquí proporcionan aún más pistas sobre cómo es el grafo, y de hecho, en muchas ocasiones es posible reconstruir el grafo completamente a partir del polinomio cromático. Sin embargo, hay que tener en cuenta que esto no siempre puede hacerse, porque dos grafos pueden tener el mismo polinomio cromático. Por ejemplo, todos los árboles (grafos con una sola componente y sin triangulitos ni ciclos mayores dentro) con el mismo número de vértices tienen el mismo polinomio cromático.

En cualquier caso, lo que salta a la vista es que a partir de un grafo, que puede ser un objeto terriblemente enrevesado, se puede obtener de modo automático un polinomio limpio y claro que inmediatamente nos va a proporcionar un montón de información que de otro modo resultaría muy difícil de conseguir. Es un poco como si por el número de DNI de una persona pudiéramos saber cómo se llamaba su primer amor.

Esperamos haber transmitido al lector nuestra admiración a quien fue capaz de concebir tan brillantes ideas, y sobre todo, nuestro entusiasmo por la belleza inherente a un tipo de matemáticas que conjugan la profundidad conceptual, la inteligibilidad y la sencillez de comprensión. Una combinación difícil de encontrar.