Problema de Hadwiger-Nelson - Hadwiger–Nelson problem

Problema no resuelto en matemáticas :

¿Cuántos colores se necesitan para colorear el plano de modo que no haya dos puntos a la distancia unitaria del mismo color?

(más problemas sin resolver en matemáticas)
Un plano de siete colores y un gráfico de distancia de cuatro unidades cromáticas en el plano (el eje de Moser ), lo que demuestra que el número cromático de un plano está limitado por arriba por 7 y por debajo por 4.
El gráfico de Golomb , el gráfico de distancia de cuatro unidades cromáticas de diez vértices de Solomon W. Golomb

En la teoría de grafos geométricos , el problema de Hadwiger-Nelson , que lleva el nombre de Hugo Hadwiger y Edward Nelson , pide el número mínimo de colores necesarios para colorear el plano de modo que no haya dos puntos a una distancia 1 entre sí que tengan el mismo color. La respuesta es desconocida, pero se ha reducido a uno de los números 5, 6 o 7. El valor correcto puede depender de la elección de axiomas para la teoría de conjuntos .

Relación con gráficos finitos

La pregunta se puede formular en términos teóricos de gráficos de la siguiente manera. Sea G el gráfico de unidad de distancia del plano: un gráfico infinito con todos los puntos del plano como vértices y con una arista entre dos vértices si y solo si la distancia entre los dos puntos es 1. El problema de Hadwiger-Nelson consiste en encontrar el número cromático de G . Como consecuencia, el problema a menudo se denomina "encontrar el número cromático del plano". Según el teorema de Bruijn-Erdős , resultado de De Bruijn & Erdős (1951) , el problema es equivalente (bajo el supuesto del axioma de elección ) al de encontrar el mayor número cromático posible de un gráfico de distancia unitaria finita.

Historia

Según Jensen y Toft (1995) , el problema fue formulado por primera vez por Nelson en 1950 y publicado por primera vez por Gardner (1960) . Hadwiger (1945) había publicado anteriormente un resultado relacionado, mostrando que cualquier cobertura del plano por cinco conjuntos cerrados congruentes contiene una unidad de distancia en uno de los conjuntos, y también mencionó el problema en un artículo posterior ( Hadwiger 1961 ). Soifer (2008) analiza ampliamente el problema y su historia.

Límites inferior y superior

El hecho de que el número cromático del plano deba ser al menos cuatro se deriva de la existencia de un gráfico de distancia unitaria de siete vértices con número cromático cuatro, denominado huso de Moser por su descubrimiento en 1961 por los hermanos William y Leo Moser . Esta gráfica consta de dos triángulos equiláteros unitarios unidos en un vértice común, x . Cada uno de estos triángulos está unido a lo largo de otro borde a otro triángulo equilátero; Los vértices y y z de estos triángulos unidos están en unidad de distancia unos de otros. Si el avión podría ser tricolor-, la coloración dentro de los triángulos obligaría Y y Z que ambos tienen el mismo color que x , pero luego, ya que Y y Z están en unidad de distancia el uno del otro, no tendríamos una coloración adecuada del gráfico de unidad de distancia del plano. Por lo tanto, se necesitan al menos cuatro colores para colorear este gráfico y el plano que lo contiene. Un límite inferior alternativo en la forma de un gráfico de distancia de cuatro unidades cromáticas de diez vértices, el gráfico de Golomb , fue descubierto aproximadamente al mismo tiempo por Solomon W. Golomb .

En 2018, el científico informático y biólogo Aubrey de Gray encontró un gráfico de unidad de distancia de 1581 vértices y no 4 colores. La prueba es asistida por computadora. El matemático Gil Kalai y el científico informático Scott Aaronson publicaron una discusión sobre el hallazgo de de Grey, y Aaronson informó verificaciones independientes del resultado de de Grey utilizando solucionadores SAT . Kalai vinculó publicaciones adicionales de Jordan Ellenberg y Noam Elkies , con Elkies y (por separado) de Gray proponiendo un proyecto de Polymath para encontrar gráficos de distancia de unidades no 4 coloreables con menos vértices que el de la construcción de Grey. A partir de 2021, el gráfico más pequeño conocido con el número cromático 5 tiene 509 vértices. La página del proyecto Polymath, Polymath (2018) , contiene más investigaciones, citas de medios y datos de verificación.

El límite superior de siete en el número cromático se deriva de la existencia de una teselación del plano por hexágonos regulares, con un diámetro ligeramente menor que uno, a los que se les pueden asignar siete colores en un patrón repetitivo para formar una coloración en 7 del plano. Según Soifer (2008) , este límite superior fue observado por primera vez por John R. Isbell .

Variaciones

El problema puede extenderse fácilmente a dimensiones superiores. Encontrar el número cromático de 3 espacios es un problema particularmente interesante. Al igual que con la versión en el avión, la respuesta no se conoce, pero se ha demostrado que es al menos 6 y como máximo 15.

En el caso n- dimensional del problema, un límite superior fácil en el número de colores requeridos encontrados en el mosaico de cubos n- dimensionales es . Un límite inferior de símplex es . Para , un límite inferior de está disponible usando una generalización del eje de Moser: un par de objetos (cada 2 simplex pegados en una faceta) que están unidos en un lado por un punto y el otro lado por una línea.

También se pueden considerar coloraciones del plano en el que los conjuntos de puntos de cada color están restringidos a conjuntos de algún tipo en particular. Tales restricciones pueden hacer que aumente el número requerido de colores, ya que impiden que ciertos colorantes se consideren aceptables. Por ejemplo, si una coloración del plano consta de regiones delimitadas por curvas de Jordan , se requieren al menos seis colores.

Ver también

Notas

Referencias

enlaces externos