Nelson-Erdős-Hadwiger probléma

A Nelson-Erdős-Hadwiger probléma a kombinatorikus geometria problémája , amelyet eredetileg az euklideszi tér színezésének vagy kromatikus számának problémájaként állítottak fel .

2022-től a feladat továbbra is nyitott .

A probléma leírása

A Nelson-Erdős-Hadwiger probléma felveti azt a kérdést, hogy egy n -dimenziós euklideszi tér hány minimális színben színezhető úgy, hogy ne legyenek egymástól 1 távolságra lévő azonos színű pontok. Ezt a számot az n - dimenziós euklideszi tér kromatikus számának nevezzük .

Ugyanez a probléma logikus egy tetszőleges metrikus tér esetén is . Általános esetben legyen metrikus tér és . Minimálisan hány színt lehet úgy festeni , hogy az azonos színű pontok között ne legyen fix távolság ? Vagy mi a metrikus tér kromatikus száma a tiltott távolsághoz képest ? $(X,\rho)$ $a>0$ $\chi ((X,\rho ),a)$ $(X,\rho )$ $a$ $(X,\rho)$ $a$

A de Bruijn-Erdős tétel szerint elegendő a feladatot a pontok összes véges részhalmazára megoldani.

Néhány eredmény

Kis méretek

Nyilvánvaló, hogy az egydimenziós tér kromatikus száma kettővel egyenlő, de a válasz még egy síkra sem ismert. Könnyű bizonyítani, hogy legalább 4 és legfeljebb 7 szín szükséges egy sík színezéséhez, de 2018-ig nem lehetett továbblépni. Ugyanakkor felmerült, hogy a válasz függhet a halmazelmélet axiómáinak megválasztásától [1] [2] . 2018-ban Aubrey de Gray megmutatta, hogy 4 szín nem elég [3] .

Aszimptotika

Legyen a Hölder-metrika . A felső korlát [4] bizonyított : $l_p$

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

és az alsó korlát [5] bebizonyosodik :

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

Egyes konkrét értékek esetében az alábbi becslések némileg megerősítettek. [6] Így megállapítható, hogy egy n-dimenziós tér kromatikus száma aszimptotikusan exponenciálisan növekszik, míg a Borsuk-probléma esetében a felső és az alsó korlát eltérő növekedési ütemű. $p,a$

Történelem

Az 1940-es évek elején tőlük függetlenül Hugo Hadwiger és Erdős Pal rendezte , nagyjából ugyanekkor Eduard Nelson és John Isbell is .

1961 - ben megjelent Hadwiger híres munkája a megoldatlan matematikai problémákról , majd elkezdték aktívan tanulmányozni a kromatikus számokat.

1976- ban M. Benda és M. Perles azt javasolta, hogy a metrikus terek legáltalánosabb összefüggésében vegyék figyelembe.

2018-ban Aubrey de Gray egy 1581 csúcsú egységnyi távolsággráfot kapott, amely nem színezhető 4 színnel. A matematikai közösség javított di Gray eredményén, 2021-ben a legkisebb ismert gráf, amely nem festhető 4 színben, 509 csúcsú [7] .

Aubrey de Gray bizonyítása után a Nelson-Erdős-Hadwiger problémára csak 5, 6 vagy 7 lehet a válasz.

Változatok és általánosítások

A Nelson-Erdős-Hadwiger probléma a kombinatorikus geometria egy másik klasszikus problémájához, a Borsuk-sejtéshez is kapcsolódik , amelyet általános esetben 1993-ban cáfoltak.

Jegyzetek

↑ Shelah, Saharon & Soifer, Alexander (2003), Választási axióma és a sík kromatikus száma , Journal of Combinatorial Theory, Series A 103 (2): 387–391, doi : 10.1016/S0097-3165(03) 00102-X , < http://www.uccs.edu/~faculty/asoifer/docs/AXIOMOFCHOICEinJCT.pdf > . Letöltve: 2013. április 29. Archiválva : 2011. június 14. a Wayback Machine -nél .
↑ Soifer, Alexander (2008), A matematikai kifestőkönyv: A színezés matematikája és alkotóinak színes élete , New York: Springer, ISBN 978-0-387-74640-1
↑ Vlagyimir Koroljev. A matematikusoknak négy szín hiányzott a sík színezéséhez . N+1 (2018. április 10.). Letöltve: 2018. április 10. Az eredetiből archiválva : 2018. április 10. (határozatlan)
↑ Larman DG, Rogers CA A halmazokon belüli távolságok realizálása az euklideszi térben// Matematika. - 1972. -19. - C. 1-24.
↑ Frankl P., Wilson RM Metszéstételek geometriai következményekkel// Combinatorica. - 1981. - 1. - C. 357-368.
↑ A. M. Raigorodsky, "A Borsuk hipotézis körül" . Letöltve: 2013. május 24. Az eredetiből archiválva : 2014. december 14.. (határozatlan)
↑ Hadwiger-Nelson probléma - Polymath Wiki . Letöltve: 2021. március 24. Az eredetiből archiválva : 2021. április 12. (határozatlan)

Irodalom

A. Raigorodsky, V. Voronov, A. Savvateev. Áttörés a síkszínezés problémájában // Kvant. - 2018. - 11. sz . — S. 2–9 . - doi : 10.4213/kvant20181101 . (Orosz)