Cambios pequeños, efectos grandes: re-colorando gráficas

Ponente(s): Mika Olsen ., Narda Cordero Michel

¿Has jugado con un cubo Rubik? Aunque no sepas resolverlo, es fácil entender de qué se trata: tienes muchas configuraciones y quieres llegar a la correcta. Una pregunta interesante (ya resuelta) es si, desde cualquier configuración, puedes llegar a la solución girando solo una parte a la vez. En matemáticas hay muchas problemas similares. En esta charla exploraremos uno dentro de la teoría de gráficas: la gráfica de re-coloración. Imagina una gráfica o digráfica, y todas las coloraciones válidas con a lo más $k$ colores. Construimos una nueva gráfica donde cada vértice representa una coloración válida, y conectamos dos vértices si las coloraciones solo difieren en el color de un vértice. La gran pregunta es: ¿Puedes transformar una coloración en otra, cambiando un vértice a la vez, sin romper las reglas? Esto depende de la conexidad de la gráfica de re-coloración, y tiene que ver con cómo los cambios locales pueden provocar cambios globales. Nos enfocaremos en coloraciones acíclicas en digráficas, donde no se permiten ciclos del mismo color. El número dicromático es el mínimo número de colores para lograr una coloración acíclica. ¿Será posible ir de cualquier coloración acíclica a otra paso a pasito? Depende . . .