Problém Nelson-Erdős-Hadwiger

Nelson-Erdős-Hadwiger problém  je problém kombinatorické geometrie , původně položený jako problém zbarvení nebo chromatického čísla Euclidean prostoru .

Od roku 2022 zůstává úkol otevřený .

Prohlášení o problému

Nelson-Erdős-Hadwigerův problém vyvolává otázku minimálního počtu barev, ve kterých lze obarvit n - rozměrný euklidovský prostor tak, že neexistují žádné body stejné barvy, které jsou od sebe vzdáleny 1. Toto číslo se nazývá chromatické číslo n - rozměrného euklidovského prostoru.

Stejný problém dává smysl pro libovolný metrický prostor . V obecném případě nechť  je metrický prostor a . Jaký je minimální počet barev , které lze namalovat tak, aby mezi body stejné barvy nemohla být pevná vzdálenost ? Nebo jaké je chromatické číslo metrického prostoru vzhledem k zakázané vzdálenosti ?

Podle de Bruijn-Erdősovy věty stačí vyřešit problém pro všechny konečné podmnožiny bodů.

Některé výsledky

Malé rozměry

Je zřejmé, že chromatické číslo jednorozměrného prostoru je rovno dvěma, ale odpověď není známa ani pro rovinu. Je snadné dokázat, že k vybarvení letadla jsou potřeba minimálně 4 a maximálně 7 barev, ale do roku 2018 nebylo možné se posunout dále. Zároveň bylo naznačeno, že odpověď může záviset na volbě axiomů teorie množin [1] [2] . V roce 2018 Aubrey de Gray ukázal, že 4 barvy nestačí [3] .

Asymptotika

Nechť  je Hölderova metrika . Horní mez [4] je dokázána :

,

a dolní mez [5] je dokázána :

U některých konkrétních hodnot jsou odhady zdola poněkud posíleny. [6] Je tedy prokázáno, že chromatické číslo n-rozměrného prostoru roste asymptoticky exponenciálně, zatímco pro Borsukův problém mají horní a dolní hranice různé rychlosti růstu.

Historie

Počátkem 40. let ho režírovali Hugo Hadwiger a Pal Erdős , nezávisle na nich, zhruba ve stejnou dobu to dělali také Eduard Nelson a John Isbell .

V roce 1961 vyšla slavná Hadwigerova práce o nevyřešených matematických problémech , po kterých se začala aktivně studovat chromatická čísla.

V roce 1976 M. Benda a M. Perles navrhli uvažovat o tom v nejobecnějším kontextu metrických prostorů.

V roce 2018 Aubrey de Gray získal graf jednotkové vzdálenosti s 1581 vrcholy, které nelze obarvit 4 barvami. Matematická komunita zlepšila di Grayův výsledek, od roku 2021 má nejmenší známý graf, který nelze vykreslit ve 4 barvách, 509 vrcholů [7] .

Po důkazu Aubrey de Gray může být odpověď na problém Nelson-Erdős-Hadwiger pouze 5, 6 nebo 7.

Variace a zobecnění

Poznámky

  1. ↑ Shelah, Saharon & Soifer, Alexander (2003), Axiom výběru a chromatické číslo roviny , Journal of Combinatorial Theory, Series A, svazek 103 (2): 387–391, doi : 10.1016/S0097-3165(03) 00102-X , < http://www.uccs.edu/~faculty/asoifer/docs/AXIOMOFCHOICEinJCT.pdf > . Získáno 29. dubna 2013. Archivováno 14. června 2011 na Wayback Machine . 
  2. ↑ Soifer, Alexander (2008), The Mathematical Coloring Book: Mathematics of Coloring and the Colorful Life of its Creators , New York: Springer, ISBN 978-0-387-74640-1 
  3. ↑ Vladimír Koroljov. Matematici postrádali čtyři barvy k obarvení letadla . N+1 (10. dubna 2018). Staženo 10. dubna 2018. Archivováno z originálu 10. dubna 2018.
  4. ↑ Larman DG, Rogers CA Realizace vzdáleností v množinách v euklidovském prostoru// Matematika. - 1972. -19. - C. 1-24.
  5. ↑ Frankl P., Wilson RM Věty o průniku s geometrickými důsledky// Combinatorica. - 1981. - 1. - C. 357-368.
  6. ↑ A. M. Raigorodsky, „Kolem hypotézy Borsuk“ . Získáno 24. 5. 2013. Archivováno z originálu 14. 12. 2014.
  7. ↑ Hadwigerův-Nelsonův problém – Polymath Wiki . Získáno 24. března 2021. Archivováno z originálu dne 12. dubna 2021.

Literatura