Problema de Hadwiger-Nelson

En la teoría geométrica de grafos , el problema de Hadwiger-Nelson , que recibe su nombre de Hugo Hadwiger y Edward Nelson , plantea la cuestión del número mínimo de colores necesarios para colorear el plano de manera que no haya dos puntos a una distancia de 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 los axiomas de la teoría de conjuntos . ^{[ 1 ]}

La pregunta puede formularse en términos de teoría de grafos de la siguiente manera. Sea G el grafo de distancia unitaria del plano: un grafo 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 hallar el número cromático de G. En consecuencia, el problema se denomina a menudo "hallar el número cromático del plano". Según el teorema de De Bruijn-Erdős , resultado de De Bruijn y Erdős (1951) , el problema es equivalente (bajo el supuesto del axioma de elección ) al de hallar el mayor número cromático posible de un grafo de distancia unitaria finito.

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

Una aplicación del problema lo relaciona con el teorema de Beckman-Quarles , según el cual cualquier mapeo del plano euclidiano (o cualquier espacio de dimensión superior) sobre sí mismo que preserve las distancias unitarias debe ser una isometría , preservando todas las distancias. ^{[ 2 ]} Las coloraciones finitas de estos espacios pueden usarse para construir mapeos desde ellos a espacios de dimensión superior que preserven las distancias unitarias pero no sean isometrías. Por ejemplo, el plano euclidiano puede mapearse a un espacio de seis dimensiones coloreándolo con siete colores de manera que no haya dos puntos a distancia uno con el mismo color, y luego mapeando los puntos por sus colores a los siete vértices de un símplex regular de seis dimensiones con aristas de longitud unitaria. Esto mapea cualquier par de puntos a distancia unitaria a colores distintos, y de ahí a vértices distintos del símplex, a distancia unitaria entre sí. Sin embargo, mapea todas las demás distancias a cero o uno, por lo que no es una isometría. Si se pudiera reducir el número de colores necesarios para colorear el plano de siete a un número menor, la misma reducción se aplicaría a la dimensión del espacio objetivo en esta construcción. ^{[ 3 ]}

El hecho de que el número cromático del plano deba ser al menos cuatro se deduce de la existencia de un grafo de distancia unitaria de siete vértices con número cromático cuatro, denominado huso de Moser tras su descubrimiento en 1961 por los hermanos William y Leo Moser . Este grafo consta de dos triángulos equiláteros unitarios unidos por un vértice común, x . Cada uno de estos triángulos está unido a lo largo de otra arista a otro triángulo equilátero; los vértices y y z de estos triángulos unidos están a distancia unitaria entre sí. Si el plano pudiera ser tricoloreado, la coloración dentro de los triángulos obligaría a que y y z tuvieran el mismo color que x , pero entonces, dado que y y z están a distancia unitaria entre sí, no tendríamos una coloración adecuada del grafo de distancia unitaria del plano. Por lo tanto, se necesitan al menos cuatro colores para colorear este grafo y el plano que lo contiene. Una cota inferior alternativa en forma de un grafo de distancia unitaria de cuatro cromáticos y diez vértices, el grafo de Golomb , fue descubierto aproximadamente al mismo tiempo por Solomon W. Golomb . ^{[ 4 ]}

El límite inferior se elevó a cinco en 2018, cuando el científico informático y biogerontólogo Aubrey de Grey encontró un grafo de distancia unitaria no 4-coloreable de 1581 vértices. La demostración está asistida por computadora. ^{[ 5 ]} 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 usando solucionadores SAT . Kalai enlazó publicaciones adicionales de Jordan Ellenberg y Noam Elkies , con Elkies y (por separado) de Grey proponiendo un proyecto Polymath para encontrar grafos de distancia unitaria no 4-coloreables con menos vértices que el de la construcción de de Grey. ^{[ 6 ]} A partir de 2021, el grafo de distancia unitaria más pequeño conocido con número cromático 5 tiene 509 vértices. ^{[ 7 ]} La página del proyecto Polymath, Polymath (2018) , contiene más investigación, 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 mediante hexágonos regulares, con un diámetro ligeramente inferior a uno, a los que se les pueden asignar siete colores en un patrón repetitivo para formar una coloración de siete colores del plano. Según Soifer (2008) , este límite superior fue observado por primera vez por John R. Isbell .

El problema puede extenderse a dimensiones superiores. Por ejemplo, al igual que en la versión en el plano, si bien se desconoce el número cromático del espacio tridimensional, se ha demostrado que es al menos 6 y como máximo 15. ^{[ 8 ]}

En el caso n -dimensional del problema, una cota superior sencilla para el número de coloraciones requeridas que se encuentra al teselar cubos n -dimensionales es${\displaystyle \lfloor 2+{\sqrt {n}}\rfloor ^{n}}$. Una cota inferior a partir de símplexes es${\displaystyle n+1}$. Para${\displaystyle n>1}$, un límite inferior de${\displaystyle n+2}$Está disponible mediante una generalización del huso de Moser: un par de objetos (cada uno dos símplexes unidos por una faceta) que están unidos por un punto en un lado y por una línea en el otro. Frankl y Wilson demostraron una cota inferior exponencial en 1981. ^{[ 9 ]}

También se pueden considerar coloraciones del plano en las que los conjuntos de puntos de cada color se restringen a conjuntos de un tipo particular. ^{[ 10 ]} Estas restricciones pueden aumentar el número de colores necesarios, ya que impiden que ciertas coloraciones se consideren aceptables. Por ejemplo, si una coloración del plano consiste en regiones delimitadas por curvas de Jordan , se requieren al menos seis colores. ^{[ 11 ]}

• Teorema de los cuatro colores
• Conjetura de Hadwiger

• O'Rourke, Joseph , "Problema 57: Número cromático del plano" , The Open Problems Project
• Mohar, Bojan (2001), El número cromático del gráfico de distancia unitaria
• Kalai, Gil (2018), Problemas de coloración para arreglos de círculos (y pseudocírculos)
• Grime, James (27 de febrero de 2019), "Un colorido problema sin resolver" , Numberphile , archivado del original el 21 de diciembre de 2021.