En la teoría de grafos geométricos , el problema de Hadwiger-Nelson , llamado así por Hugo Hadwiger y Edward Nelson , pregunta por el número mínimo de colores necesarios para colorear el plano de modo 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 axiomas para la teoría de conjuntos . [1]
La cuestión 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 encontrar el número cromático de G. En consecuencia, el problema se suele denominar "encontrar el número cromático del plano". Por el teorema de de Bruijn–Erdős , un 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 grafo de distancia unitaria finito.
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, que mostraba que cualquier recubrimiento 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 el problema y su historia en profundidad.
Una aplicación del problema lo conecta con el teorema de Beckman-Quarles , según el cual cualquier aplicación del plano euclidiano (o cualquier espacio de dimensión superior) a sí mismo que preserve distancias unitarias debe ser una isometría , preservando todas las distancias. [2] Las coloraciones finitas de estos espacios se pueden usar para construir aplicaciones de ellos a espacios de dimensión superior que preserven distancias pero no sean isometrías. Por ejemplo, el plano euclidiano se puede aplicar a un espacio de seis dimensiones coloreándolo con siete colores de modo que ningún par de puntos a una distancia de uno tenga el mismo color, y luego asignando los puntos por sus colores a los siete vértices de un símplex regular de seis dimensiones con aristas de longitud unitaria. Esto asigna dos puntos cualesquiera a una distancia unitaria a colores distintos, y desde allí a vértices distintos del símplex, a una distancia unitaria 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 debe ser al menos cuatro se desprende de la existencia de un grafo de distancia unitaria de siete vértices con número cromático cuatro, llamado huso de Moser después de su descubrimiento en 1961 por los hermanos William y Leo Moser . Este grafo 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 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 ser tricolor, la coloración dentro de los triángulos obligaría a y y z a tener ambos el mismo color que x , pero entonces, como y y z están a una 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. Un límite inferior alternativo en forma de grafo de distancia unitaria de cuatro vértices cromáticos, 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 gerontólogo Aubrey de Grey encontró un grafo de distancia unitaria de 1581 vértices y no coloreable de 4. La prueba 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 utilizando solucionadores SAT . Kalai vinculó 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 coloreables de 4 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 investigaciones, citas de medios y datos de verificación.
El límite superior de siete en el número cromático se desprende de la existencia de una teselación del plano formada por 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 7 del plano. Según Soifer (2008), este límite superior fue observado por primera vez por John R. Isbell .
El problema se puede extender fácilmente a dimensiones superiores. Encontrar el número cromático del espacio 3 es un problema particularmente interesante. Al igual que con la versión en el plano, la respuesta no se conoce, pero se ha demostrado que es al menos 6 y como máximo 15. [8]
En el caso n -dimensional del problema, un límite superior fácil para el número de coloraciones requeridas encontradas al colocar cubos n -dimensionales en mosaico es . Un límite inferior a partir de símplex es . Para , un límite inferior de está disponible usando una generalización del huso de Moser: un par de objetos (cada uno dos símplex pegados entre sí en una faceta) que están unidos en un lado por un punto y en el otro lado 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 el número requerido de colores aumente, ya que impiden que ciertas coloraciones se consideren aceptables. Por ejemplo, si una coloración del plano consiste en regiones limitadas 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 )