Problema de Hadwiger-Nelson

Archiu:Hadwiger-Nelson.svg

Una coloració de sèt colors del pla i un gràfic de distància unitària de quatre cromas en el pla (el huso de Moser), lo que demostra que el número cromàtic d'un pla està llimitat per dalt per 7 i per avall per 4

Archiu:GolombGraphProperties.svg

El grafo de Golomb, el grafo de distància unitària de quatre colors i dèu vèrtiços descobert per Solomon W. Golomb

En teoria de grafos geomètrica, el problema de Hadwiger-Nelson, cridat aixina per Hugo Hadwiger i Edward Nelson, consistix en buscar el número mínim de colors necessaris per a colorear el pla de modo que no hi haja dos punts a una distància d'1 entre sí que tinguen el mateix color. La resposta es desconeix, pero s'ha reduït a un dels números 5, 6 o 7. El valor correcte pot dependre de l'elecció dels axioma per a la teoria de conjunts associada.

Relació en grafos finitos

La pregunta pot formular-se en térmens de la teoria de grafos de la següent manera. Siga G el gràfic de distància unitària del pla: un grafo infinit en tots els punts del pla com vèrtiços i en una aresta entre dos vèrtiços si, i solament si, la distància entre els dos punts és 1. El problema de Hadwiger-Nelson consistix en trobar la coloració de grafos de G. Com a conseqüència, el problema sol denominar-se "trobar el número cromàtic del pla". Segons el teorema de De Bruijn-Erdős, un resultat de de Bruijn y Erdős (1951), el problema és equivalent (baixe el supòsit del axioma d'elecció) a trobar el major número cromàtic possible d'un grafo de distàncies unitàries finitas.

Història

Segons Jensen y Toft (1995), el problema va ser formulat per primera volta per Nelson en 1950 i publicat per primera volta per Gardner (1960). Hadwiger (1945) havia publicat prèviament un resultat relacionat, que demostrava que qualsevol recobriment del pla per cinc conjunts tancats congruents conté una distància unitària en un dels conjunts, i també va mencionar el problema en un artícul posterior Plantilla:Harv. Soifer (2008) va analisar el problema i la seua història extensament.

Una aplicació del problema ho conecta en el teorema de Beckman-Quarles, segons el qual qualsevol aplicació del pla euclídeo (o qualsevol espai de dimensió superior) sobre sí mateixa que preserve les distàncies unitàries deu ser una isometría, que preserva totes les distàncies.Plantilla:Sfnp Les coloració finitas d'estos espais permeten construir aplicacions a partir d'ells en espais de dimensions superiors que conserven les distàncies, pero no són isometría. Per eixemple, el pla euclídeo es pot aplicar a un espai de sis dimensions coloreándolo en sèt colors, de modo que cap parell de punts a una distància donada d'un color tinga el mateix color, i després aplicant els punts, segons els seus colors, als sèt vèrtiços d'un símplex de sis dimensions en arestes de llongitut unitària. Açò aplica dos punts qualssevol a una distància d'un color a colors distints, i d'ahí a vèrtiços distints del símplex, separats per una distància unitària. No obstant, aplica totes les demés distàncies a zero o un, per lo que no és una isometría. Si el número de colors necessaris per a colorear el pla es poguera reduir de sèt a un número menor, la mateixa reducció s'aplicaria a la dimensió de l'espai objectiu en esta construcció.Plantilla:Sfnp

Vore també

• Teorema dels quatre colors

Bibliografia

• (doi trencat: 6 de juliol de 2025)
• (074)
• «Polymath16, seventeenth thread: Declaring victory».Consultat el 16 d'agost de 2021.

• «Axiom of choice and chromatic number of the plane».Journal of Combinatorial Theory, Séries A.103(2)

387–391.doi:10.1016/S0097-3165(03)00102-X.