Problema de Nelson-Erdős-Hadwiger

El problema de Nelson-Erdős-Hadwiger es un problema de geometría combinatoria , originalmente planteado como un problema de coloración o número cromático del espacio euclidiano .

A partir de 2022, la tarea permanece abierta .

Planteamiento del problema

El problema de Nelson-Erdős-Hadwiger plantea la cuestión del número mínimo de colores en los que se puede colorear un espacio euclidiano de n dimensiones de forma que no haya puntos del mismo color que estén a una distancia de 1 entre sí. Este número se denomina número cromático del espacio euclidiano de n dimensiones.

El mismo problema tiene sentido para un espacio métrico arbitrario . En el caso general, sea un espacio métrico y . ¿Cuál es el número mínimo de colores que se pueden pintar de forma que no pueda haber una distancia fija entre puntos del mismo color ? ¿O cuál es el número cromático del espacio métrico con respecto a la distancia prohibida ? $(X,\rho)$ ${\ estilo de visualización a> 0}$ ${\ estilo de visualización \ chi ((X, \ rho), a)}$ $(X,\rho)$ $a$ $(X,\rho)$ $a$

Según el teorema de de Bruijn-Erdős , basta con resolver el problema para todos los subconjuntos finitos de puntos.

Algunos resultados

Pequeñas dimensiones

Es obvio que el número cromático del espacio unidimensional es igual a dos, pero la respuesta no se conoce ni siquiera para un plano. Es fácil probar que se requieren al menos 4 y como máximo 7 colores para colorear un avión, pero no fue posible avanzar más hasta 2018. Al mismo tiempo, se sugirió que la respuesta puede depender de la elección de los axiomas de la teoría de conjuntos [1] [2] . En 2018, Aubrey de Grey demostró que 4 colores no son suficientes [3] .

Asintóticos

Sea la métrica de Hölder . El límite superior [4] se demuestra : $l_p$

{\displaystyle \chi ((\mathbb {R} ^{n},l_{p}),a)\leqslant (3+o(1))^{n))

y se demuestra el límite inferior [5] :

{\displaystyle \chi ((\mathbb {R} ^{n},l_{p}),a)\geqslant (1207...+o(1))^{n))

Para algunos valores específicos , las estimaciones de abajo se fortalecen un poco. [6] Así, se establece que el número cromático de un espacio n-dimensional crece asintóticamente exponencialmente, mientras que para el problema de Borsuk , los límites superior e inferior tienen diferentes tasas de crecimiento. $pag$

Historia

A principios de la década de 1940, fue dirigida por Hugo Hadwiger y Pal Erdős , independientemente de ellos, casi al mismo tiempo, también estaba siendo realizada por Eduard Nelson y John Isbell .

En 1961, se publicó el famoso trabajo de Hadwiger sobre problemas matemáticos no resueltos , después de lo cual los números cromáticos comenzaron a estudiarse activamente.

En 1976, M. Benda y M. Perles propusieron considerarlo en el contexto más general de los espacios métricos.

En 2018, Aubrey de Grey obtuvo un gráfico de distancia unitaria con 1581 vértices, que no se puede colorear con 4 colores. La comunidad matemática ha mejorado el resultado de di Gray, a partir de 2021, el gráfico más pequeño conocido que no se puede pintar en 4 colores tiene 509 vértices [7] .

Después de la prueba de Aubrey de Gray, la respuesta al problema de Nelson-Erdős-Hadwiger solo puede ser 5, 6 o 7.

Variaciones y generalizaciones

El problema de Nelson-Erdős-Hadwiger también está relacionado con otro problema clásico de la geometría combinatoria, la conjetura de Borsuk , que fue refutada en el caso general en 1993.

Notas

↑ Shelah, Saharon & Soifer, Alexander (2003), Axioma de elección y número cromático del plano , Journal of Combinatorial Theory, Serie A, volumen 103 (2): 387–391, doi : 10.1016/S0097-3165(03) 00102-X , < http://www.uccs.edu/~faculty/asoifer/docs/AXIOMOFCHOICEinJCT.pdf > . Consultado el 29 de abril de 2013. Archivado el 14 de junio de 2011 en Wayback Machine .
↑ Soifer, Alexander (2008), The Mathematical Coloring Book: Matemáticas de la coloración y la colorida vida de sus creadores , Nueva York: Springer, ISBN 978-0-387-74640-1
↑ Vladímir Korolev. Los matemáticos carecían de cuatro colores para colorear el plano . N+1 (10 de abril de 2018). Consultado el 10 de abril de 2018. Archivado desde el original el 10 de abril de 2018. (indefinido)
↑ Larman DG, Rogers CA La realización de distancias dentro de conjuntos en el espacio euclidiano// Mathematika. - 1972. -19. - C. 1-24.
↑ Frankl P., Wilson RM Teoremas de intersección con consecuencias geométricas// Combinatorica. - 1981. - 1. - C. 357-368.
↑ A. M. Raigorodsky, "Alrededor de la hipótesis de Borsuk" . Consultado el 24 de mayo de 2013. Archivado desde el original el 14 de diciembre de 2014. (indefinido)
↑ Problema de Hadwiger-Nelson - Polymath Wiki . Consultado el 24 de marzo de 2021. Archivado desde el original el 12 de abril de 2021. (indefinido)

Literatura

A. Raigorodsky, V. Voronov, A. Savvateev. Avance en el problema de la coloración del avión // Kvant. - 2018. - Nº 11 . — P. 2–9 . -doi : 10.4213 / kvant20181101 . (Ruso)