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. Se desconoce la respuesta, 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 se puede formular en términos de teoría de grafos de la siguiente manera. Sea G la gráfica de distancia unitaria del plano: una gráfica infinita con todos los puntos del plano como vértices y con una arista entre dos vértices si y sólo 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 suele denominarse "encontrar 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 encontrar el mayor número cromático posible de un gráfico de distancia unitaria finita.
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.
Una aplicación del problema lo conecta con el teorema de Beckman-Quarles , según el cual cualquier mapeo del plano euclidiano (o cualquier espacio dimensional superior) consigo mismo que conserve distancias unitarias debe ser una isometría , que preserve todas las distancias. [2] Las coloraciones finitas de estos espacios se pueden utilizar para construir asignaciones a partir de ellos a espacios de dimensiones superiores que preservan las distancias pero no son isometrías. Por ejemplo, el plano euclidiano se puede mapear en un espacio de seis dimensiones coloreándolo con siete colores de modo que no haya dos puntos a una distancia de uno que tengan el mismo color, y luego mapeando los puntos por sus colores a los siete vértices de un espacio de seis dimensiones. simplex regular dimensional con aristas de longitud unitaria. Esto asigna dos puntos cualesquiera a una unidad de distancia a colores distintos, y desde allí a distintos vértices del simplex, a una unidad de distancia entre sí. Sin embargo, asigna todas las demás distancias a cero o uno, por lo que no es una isometría. Si el número de colores necesarios para colorear el plano pudiera reducirse 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 desprende de la existencia de un gráfico 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 . Esta gráfica consta de dos triángulos equiláteros unitarios unidos por un vértice común, x . Cada uno de estos triángulos está unido por otra arista a otro triángulo equilátero; los vértices y y z de estos triángulos unidos están a una distancia unitaria entre sí. Si el plano pudiera tener tres colores, la coloración dentro de los triángulos obligaría a y y z a tener ambos el mismo color que x , pero entonces, dado que y y z están a una unidad de distancia entre sí, no tendríamos una coloración adecuada. de la gráfica de distancia unitaria del avión. Por lo tanto, se necesitan al menos cuatro colores para colorear este gráfico y el plano que lo contiene. Aproximadamente al mismo tiempo , Solomon W. Golomb descubrió un límite inferior alternativo en forma de un gráfico de distancia de cuatro unidades cromáticas de diez vértices, el gráfico de Golomb . [4]
El límite inferior se elevó a cinco en 2018, cuando el científico informático y gerontólogo Aubrey de Gray encontró un gráfico de unidades de distancia de 1581 vértices y sin cuatro colores. La prueba está asistida por ordenador. [5] El matemático Gil Kalai y el 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 Polymath para encontrar gráficos de distancia unitarias que no se pueden colorear con 4 colores y con menos vértices que el de la construcción de De Grey. [6] A partir de 2021, el gráfico 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 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 un mosaico del plano formado por hexágonos regulares, con un diámetro ligeramente menor que uno, a los que se pueden asignar siete colores en un patrón repetido 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 fácilmente a dimensiones superiores. Encontrar el número cromático del espacio tridimensional es un problema particularmente interesante. Al igual que con la versión del avión, se desconoce la respuesta, pero se ha demostrado que es al menos 6 y como máximo 15. [8]
En el caso de n dimensiones del problema, un límite superior sencillo para el número de coloraciones requeridas que se encuentran al colocar mosaicos de cubos de n dimensiones es . Un límite inferior de los simplex es . Para , está disponible un límite inferior utilizando una generalización del huso de Moser: un par de objetos (cada uno de ellos dos símplex pegados en una faceta) que están unidos en un lado por un punto y en el otro por una línea. Frankl y Wilson demostraron un límite inferior exponencial en 1981. [9]
También se pueden considerar coloraciones del plano en las que los conjuntos de puntos de cada color están restringidos a conjuntos de algún tipo particular. [10] Tales restricciones pueden hacer que aumente el número requerido de colores, ya que impiden que ciertos colorantes se consideren aceptables. Por ejemplo, si la coloración del plano consta de regiones delimitadas por curvas de Jordan , entonces se requieren al menos seis colores. [11]
{{citation}}: Mantenimiento CS1: DOI inactivo a partir de mayo de 2024 ( enlace ) Mantenimiento CS1: fecha y año ( enlace )