Jot Down Cultural Magazine – Entusiasmo por el polinomio cromático

Entusiasmo por el polinomio cromático

Publicado por

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:

El grafo de Petersen y un grafo coloreado. Fuente: Wikicommons.

El grafo de Petersen y un grafo coloreado. Fuente: Wikicommons.

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, PG(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.

George Birkhoff en los años treinta. (DP)

George Birkhoff en los años treinta. (DP)

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 anxn +an-1xn-1+…+a0, donde los an son constantes y x es una variable. Por ejemplo, 3x2+4x+5 o 4x7+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 kn, 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 Ga 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 Ga es un grafo en el cual identificamos los dos vértices de a en uno solo. Por tanto, Ga tiene un vértice menos que G, la arista Ga 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 Ga. Se realiza, de hecho, un «pegado» en el grafo.

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

Pensemos ahora en una coloración de Ga. 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 Ga (con el vértice distinguido de Ga 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 Ga con k colores como coloraciones de Ga con k colores más coloraciones de G con k colores. Escrito resumidamente (!y en esta expresión está todo!):

PG(k) = PG-a(k) – PGa(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 Ga y Ga, acabaremos escribendo PG(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, PG(k) también lo será.

De este modo, además de ver que PG(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 a0 del polinomio cromático es siempre cero.
  • Todos los coeficientes del polinomio cromático son distintos de cero a partir de un cierto aj.
  • 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.

15 comentarios

  1. Muy interesante el artículo, ojalá más gente se interese por las matemáticas poco a poco.

    Un ppequeño apunte: ¿no queda raro eso de “un ironman diario tres veces al día”? O es un ironman al día o son tres. Aunque yo supongo que sufriría un paro cardíaco con intentar hacer medio

    • Me parece que el autor no ha entendido bien la teoría de grafos; no parece acabar de captar las relaciones binarias representacionales establecidas entre vértices y aristas con sus respectivos nodos, tal como ya dijera Leonhard Euler en su problema de los Puentes de Koenigsberg.

      Ademñas, ha ignorado el principio de adyacencia que caracteriza las propiedades de los grafos.

      • Que yo sepa, las “las relaciones binarias representacionales establecidas entre vértices y aristas con sus respectivos nodos” no tienen nada que ver con la teoría de grafos. En todo caso, con la aplicación de la teoría de grafos, pero uno puede trabajar en la teoría sin necesidad de preocuparse por esas cosas.

        “Ademñas, ha ignorado el principio de adyacencia que caracteriza las propiedades de los grafos.”
        Esa frase ni siquiera tiene sentido.

        Por favor, si vas a venir a trolear y a hacer como que sabes mucho, lo menos que podemos pedirte es que de hecho lo sepas. Y no es el caso.

  2. Gracias por el artículo.

    Creo que hay un error en:
    “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 kn, 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 nueve coloraciones diferentes.”

    Serían ocho coloraciones no? 2 elevado a 3.

    Gracias!

    • Gracias, Adrian, de hecho no tenía ni idea de lo que estaba diciendo (las tablas de multiplicar ya me van justas) pero pretendiar soltar una parrafada y que alguien contestase indignado, llevaba ya dos días esperando la respuesta y había perdido toda esperanza. Gracias!!!!!

  3. Es un pequeño error tipográfico. El n es un superíndice, lo que pasa es que se ve demasiado grande ;) Gracias!

  4. Y tienes razón, por supuesto, debe poner ocho coloraciones, no nueve. Eso es errata mía, lo rectificamos en cuanto sea posible. Gracias!

  5. Pingback: Ramón Flores: Entusiasmo por el polinomio cromático | Texto casi Diario

  6. Pingback: Ramón Flores: Entusiasmo por el polinomio cromático | Texto casi Diario

  7. Preguntó Salvador Dalí a una persona cúantos colores veía en un árbol. Pues el verde claro y el oscuro le contestó, más o menos. Yo veo miles de verdes respondió Dalí. He entendido que una cosa son vértices y otra aristas. Figuras inscritas completas. Pero un único vértice de una figura completa forma parte de otra figura completa por lo cual el color de este vértice seria la aleación de los colores asignados a las figuras completas de que forma parte -¿Son triángulos, son multilados, regulares o irregulares?- Es decir que necesitaríamos una paleta supernumeraria y por otra parte el ojo humano reconoce o distingue hasta cierto tipo de tonalidad. De ahí que se pretenda simplificar en dos, tres , cuatro etc. Es como la música, donde el intervalo entre un tono, se puede subdividir pero llegará que el oído ya no sabrá reconocer la desafinación. Grafos, vértices, polinomios, álgebra . . . y que sirven para ver a golpe de vista una condición en la exacta que deriva. Informática, genética y etc. Usted se explica de maravilla. Es sin duda un buen y apasionado matemático. Lamentamos no estar a la altura para la resolución e innovación. Ya sabe la educación media que tuvimos. Un saludo y excelente usted.

    • Hola Brigett, yo también soy un lector de este artículo al que le ha gustado mucho. Me gustaría decirle que estoy de acuerdo con usted en que la educación básica e intermedia de Matemáticas que se imparte en nuestro país es, en general, escasa y de mala calidad. Podríamos discutir largamente sobre las razones de esta anomalía tan perjudicial para todos, pero me gustaría, por el contrario, aportarle una dosis de esperanza.

      En efecto, nunca es tarde para aprender. Pienso que un ingrediente esencial en el aprendizaje de las Matemáticas, que estoy seguro de que pueden proporcionarle gran placer intelectual, es la perseverancia. Con un poco de esfuerzo puede comprender usted todo lo que se proponga. Hay excelentes libros de divulgación en español, quizás yo no sea el más indicado para aconsejarle pero puedo recomendarle uno: Matemáticas, una breve introducción, de Timothy Gowers. Es un libro muy corto pero fascinante.

      Espero que le guste.

      Matemáticamente suyo,
      Néstor

      • ¿Educación básica escasa? Depende. Yo soy profesor de matemáticas de secundaria y, en mi opinión, uno de los principales problemas con el currículo matemático es que es demasiado extenso (demasiados contenidos). Como consecuencia no da tiempo de afianzar los conceptos básicos ni de practicar lo más importante: la resolución de problemas y el razonamiento matemático.

  8. ¡Felicidades por el artículo! Muy interesante, me quedé con una pregunta: ¿es fácil demostrar que el polinomio cromático no depende de la elección de aristas que quitamos?

    Muchas gracias y un saludo,
    Néstor

  9. Es un placer ver artículos de matemáticas que vayan más allá de curiosidades y que no consideren al lector estúpido… felicidades por el artículo, en el que abordas un tema nada trivial, aunque sobradamente interesante.

    Una única crítica para mejorar: En la figura de los grafos (dcha) hay una arista que conecta dos vértices del mismo color (azules). Por lo tanto, en este caso, el pie de página diciendo “un grafo coloreado” puede inducir a confusión, puesto que el tema de la coloración consiste, precisamente en evitar esta situación.

    Un abrazo
    Bernat

  10. @Nestor Es fácil ver que el polinomio no depende de la elección de aristas, porque la fórmula principal (dejarlo en función del grafo
    diferencia y el grafo cociente) es válida quitemos la arista que quitemos, y por tanto el proceso de iteraciones debe llevar indefectiblemente al mismo polinomio. El lado izquierdo de la igualdad nunca cambia. Por otro lado, muy buena la elección de Gowers,
    gurú de la matemática discreta.

    @Bernat Tienes razón, ahí sólo quería ilustrar el concepto de grafo y se me pasó esa arista. Espero que no induzca a demasiada confusión. Gracias ;)

Responder

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *

*

Uso de cookies

Este sitio web utiliza cookies para que usted tenga la mejor experiencia de usuario. Si continúa navegando está dando su consentimiento para la aceptación de las mencionadas cookies y la aceptación de nuestra política de cookies, pinche el enlace para mayor información.

ACEPTAR
Aviso de cookies