Colorear para matemáticos

¿Cómo se pinta un plano?

Uno de los problemas más hermosos y aún sin resolver de las matemáticas está formulado de la siguiente manera: tratemos de pintar una colección de puntos en el plano conectados por líneas del mismo tamaño de tal modo que no haya dos puntos conectados que tengan el mismo color. ¿Cuál es el número mínimo de colores requeridos para lograr este fin? A pesar de la aparente simplicidad de este problema (llamado problema de Hadwinger-Nelson), durante los casi 70 años de existencia del mismo, todavía no hay una respuesta exacta, no obstante los esfuerzos de los científicos más prominentes en esta área.

Hace unos 60 años, los matemáticos descubrieron que este número mínimo de colores era cuatro, cinco, seis o siete. Ese resultado no fue mejorado sino hasta en abril del año pasado cuando el británico Aubrey de Grey publicó un artículo en el que demostró que cuatro colores no basta, reduciendo las posibilidades a cinco, seis o siete.

Uno de los hechos emocionantes de este hallazgo es que el propio Aubrey De Grey no es un matemático, su profesión está relacionada con la biomedicina: es uno de los principales investigadores de la Fundación SENS, una organización no gubernamental (ONG) dedicada a la investigación para prolongar la expectativa de vida del ser humano. Quizás lo más cercano a las matemáticas son sus artículos sobre inteligencia artificial en medicina.  

N+1 quiso entender la historia del problema de colorear el plano y contar cómo este matemático aficionado fue capaz de dar un nuevo paso importante hacia su solución.

El grafo de Moser es un grafo de distancia unitaria que requiere mínimo cuatro colores y su existencía puede ser usada para demostrar que el número cromático en el plano es al menos cuatro.

Formulación del problema

El problema del número cromático del plano

¿Cuál es el número mínimo de colores necesario para poder pintar el plano de tal manera que no tenga dos puntos del mismo color si todos están situados a la misma distancia entre sí?

Hoy en día nadie pone en duda que la tarea de colorear el plano proviene del campo de la teoría de grafos. El problema apareció a mediados del siglo XX, y, aparentemente, fue inventado por varios matemáticos de manera independiente, incluyendo al famoso matemático húngaro Paul Erdős. En el libro “Mathematical Coloring Book” Alexander Soifer habla de los resultados de sus intento por establecer la autoría del problema. Después de haber entrevistado a varios matemáticos, Soifer llegó a la conclusión de que el primero que formuló el problema fue Edward Nelson, entonces un estudiante de la Universidad de Chicago. En 1950, Edward Nelson se dedicó al problema del colorear regiones en el plano, que más tarde se conoció como el teorema de los cuatro colores.

La forma de colorear el plano en nueve colores.

Grafo Planar

Un grafo es un conjunto de puntos (vértices) y segmentos (aristas) que los conectan. Un grafo planar es uno que se puede dibujar en un plano sin intersectar los bordes.

¿Cuál es el menor número de colores suficiente para colorear todos los vértices de cualquier grafo planar de manera que no haya dos vértices conectados por un borde?


La forma de colorear el plano en 7 colores.

 

Este problema tiene una formulación equivalente más simple: tomemos un mapa dibujado en el plano. Se compone de áreas cerradas que bordean entre sí. ¿Puede este mapa ser siempre coloreado con cuatro colores para que no haya dos países del mismo color que tengan una frontera en común?

Nelson sugirió que en lugar de colorear todo tipo de grafos planares, se puede construir un grafo enorme que contiene todos los grafos planares posibles. Entonces si se demuestra que este “supergrafo” está coloreado de acuerdo con las reglas de los cuatro colores, entonces por consecuencia se demostrará el teorema.

La construcción de tal “supergrafo” es la siguiente: tomamos todos (sin excepción) los puntos del plano. Serán los vértices de nuestro grafo. Si un par de vértices están a una distancia de una unidad (por ejemplo, un centímetro), los conectaremos por un segmento - los cuales se convertirán en las aristas de nuestro grafo. Claramente, este grafo no será un grafo planar. La pregunta que Nelson se hizo fue la siguiente: ¿Pueden los vértices de tal grafo ser coloreados usando solo cuatro colores?


Coloreando el plano en 7 colores.

Esta formulación, después de una cuidadosa consideración, es consistente con el problema habitual del teorema de los cuatro colores. Solo necesitamos ver detrás de cada punto del plano de la parte superior del grafo, conectado por un gran número de aristas a otros vértices.

Desafortunadamente, la idea de Nelson no ayudó a resolver el problema de los cuatro colores. Este teorema no fue resuelto sino hasta 26 años después por Kenneth Appel y Wolfgang Haken, y se basó en la clasificación de todos los posibles grafos planares (mapas) en 1,936 configuraciones diferentes, y para cada una de las cuales se puede verificar su coloración. Esta demostración fue la primera por computadora de un problema matemático complejo.
 

Un número escurridizo

La peculiaridad del problema del número cromático es que, aparentemente, no existe un enfoque general o una herramienta para resolverlo (o al menos no existe todavía). Por otro lado, la forma de colorear los grafos ha sido bien estudiada y se descubrió un teorema importante, que apareció independientemente del problema sobre el grafo planar en 1951 e indica de alguna manera cómo podría ser la solución. Este es el teorema de De Bruijin-Erdős.

Volvamos a la formulación dada al problema de los números cromáticos por Edward Nelson. De hecho, nuestro objetivo es pintar un enorme grafo infinito, en el que los vértices son todos, sin excepción, los puntos del plano real. De Bruijin y Erdős estudiaron cómo se relaciona la coloración del grafo infinito y sus subgrafos. Resulta que el número cromático del grafo infinito, si es que lo hay, es igual al número cromático máximo de sus subgrafos finales.


Los colores de arriba contienen un triángulo monocromático, los de abajo no.
Aubrey de Grey / arXiv.org, 2018

 

Ya conocemos que el número cromático del plano no excede de siete. Así, si es igual a, digamos, seis, podemos construir con precisión un grafo finito con distancias unitarias entre los vértices, para una coloración "correcta" que requerirá al menos seis colores. Desafortunadamente, para demostrar que no hay otro grafo con un número cromático igual a siete no existe, con la ayuda de este teorema no funcionará. Pero si encontramos un grafo con un número cromático igual a siete, el problema del número cromático del plano finalmente se resolverá.

Cabe señalar que la demostración del teorema requiere el uso de un axioma especial de la teoría de conjuntos - el axioma de elección. Sin entrar en detalles, notamos que no todos los sistemas axiomáticos lo incluyen y en algunos casos especiales este teorema puede ser incorrecto. Así, el número cromático de planos en teoría también puede depender de la elección de los axiomas.


 

Estructura de 52 hexágonos, que tiene garantizado un triángulo monocromático. (Aubrey D.N.J. De Grey / arXiv.org, 2018)

 

¿Cuál es el siguiente paso?

Inmediatamente después de la publicación del preimpreso en arXiv.org por Aubrey De Grey, los matemáticos profesionales comenzaron a comprobar las demostraciones. A pesar de cierto escepticismo, este aficionado ha avanzado en una tarea en la que nadie había podido avanzar en casi 60 años. Resultó que la solución era generalmente correcta. Esto fue confirmado por múltiples revisiones independientes de computadora. Sin embargo, hubo un error con el grafo simplificado, resultó que todavía estaba coloreado en cuatro colores. Pero este "error", como lo llaman los matemáticos, se corrige fácilmente añadiendo 18 vértices, que De Grey eliminó en los últimos pasos de la simplificación.

Después de esto, De Grey en conjunto con Terrence Tao, publicó una nueva tarea en el sitio web de Polymath Projects para encontrar posibles simplificaciones al grafo de cinco colores. Hasta la fecha, el mejor resultado ha sido sugerido por Marijn Heule de la Universidad de Texas, reduciendo el número de vértices a 826.

Pero el propósito principal de encontrar una simplificación no es para simplificar la evidencia. Un grafo simple de cinco colores puede ser la base para construir un grafo de seis colores, si existe. Además, se puede intentar hacer construcciones similares para mejorar los límites del problema sobre el número cromático en dimensiones superiores.

 


 

Estructura cuyo centro está garantizado que no tiene triángulos monocromáticos. (Aubrey D.N.J. De Grey / arXiv.org, 2018)

 

¿Por qué harías eso?

La tarea de colorear los grafos tiene en realidad aplicaciones bastantes concretas en programación y optimización. En cierto sentido, incluso el sudoku puede reducirse a colorear un grafo. Pero, por supuesto, muchos problemas matemáticos no se resuelven por el bien de las aplicaciones prácticas. La mejor ilustración de este pensamiento es una cita del libro de Alexander Soifer "Mathematical Coloring Book":

"Durante muchos años he estado convencido de que el número cromático será igual a 7 o 6. Una vez Paul Erdős dijo que Dios tiene un libro infinito que contiene todos los teoremas y sus mejores demostraciones, y se lo muestra a algunos por un momento. Si me honraran con tal honor y pudiera elegir, le pediría que mirara la página con la tarea del número cromático del plano. ¿Y tú?".


 

Un grafo de 826 vértices con distancias unitarias entre los vértices conectados, que no pueden ser coloreados correctamente con solo cuatro colores.
Marijn Heule

Vladimir Korolev

Traducido y adaptado por Viviana Márquez

Esta noticia ha sido publicada originalmente en N+1, ciencia que suma.

Sobre N+1: Es la primera revista online de divulgación científica y tecnológica que permite la reproducción total o parcial de sus contenidos por medios de comunicación, bloggers e influencers, realizando la mención del texto y el enlace a la web: “Esta noticia ha sido publicada originalmente en la revista N+1, ciencia que sumawww.nmas1.org”.​​

Suscríbete

Déjanos tu mail para recibir nuestro boletín de noticias

La confirmación ha sido enviada a tu correo.