Hadwiger – Nelsonův problém - Hadwiger–Nelson problem
Nevyřešený problém v matematice: Kolik barev je potřeba k vybarvení roviny tak, aby žádné dva body v jednotkové vzdálenosti nebyly stejné barvy? (více nevyřešených úloh z matematiky) |
v teorie geometrických grafů, Hadwiger – Nelsonův problém, pojmenoval podle Hugo Hadwiger a Edward Nelson, požaduje minimální počet barev potřebných k vybarvení souboru letadlo takové, že žádné dva bodů ve vzdálenosti 1 od sebe mají stejnou barvu. Odpověď není známa, ale byla zúžena na jedno z čísel 5, 6 nebo 7. Správná hodnota může záviset na volbě axiomů pro teorie množin.[1]
Vztah ke konečným grafům
Otázku lze formulovat teoretická graf pojmy následovně. Nechat G být graf jednotkové vzdálenosti roviny: nekonečný graf se všemi body roviny jako vrcholy as hranou mezi dvěma vrcholy právě tehdy, když je vzdálenost mezi dvěma body 1. Hadwiger-Nelsonův problém spočívá v nalezení chromatické číslo z G. V důsledku toho se problém často nazývá „nalezení chromatického čísla roviny“. Podle de Bruijn – Erdősova věta, výsledek de Bruijn a Erdős (1951), problém je ekvivalentní (za předpokladu axiom volby ) k nalezení největšího možného chromatického čísla grafu vzdálenosti konečné jednotky.
Dějiny
Podle Jensen & Toft (1995), problém poprvé formuloval Nelson v roce 1950 a poprvé ho publikoval Gardner (1960). Hadwiger (1945) dříve publikoval související výsledek, který ukazuje, že jakékoli krytí letadla pěti shodnými uzavřenými sadami obsahuje jednotkovou vzdálenost v jedné ze sad, a problém zmínil také v pozdějším článku (Hadwiger 1961 ). Soifer (2008) podrobně pojednává o problému a jeho historii.
Dolní a horní mez
Skutečnost, že chromatické číslo roviny musí být alespoň čtyři, vyplývá z existence grafu jednotkové vzdálenosti sedmi vrcholů s chromatickým číslem čtyři, který se jmenuje Moser vřeteno po objevu v roce 1961 bratry Williamem a Leo Moser. Tento graf se skládá ze dvou jednotek rovnostranné trojúhelníky připojil se ke společnému vrcholu, X. Každý z těchto trojúhelníků je spojen podél dalšího okraje s jiným rovnostranným trojúhelníkem; vrcholy y a z těchto spojených trojúhelníků jsou v jednotkové vzdálenosti od sebe. Pokud by rovina mohla být tříbarevná, zbarvení uvnitř trojúhelníků by mělo sílu y a z oba mají stejnou barvu jako X, ale potom, protože y a z jsou v jednotkové vzdálenosti od sebe, neměli bychom správné zbarvení grafu jednotkové vzdálenosti v rovině. Proto jsou pro zbarvení tohoto grafu a roviny, která ho obsahuje, zapotřebí alespoň čtyři barvy. Alternativní dolní mez ve formě grafu vzdálenosti deseti vrcholů se čtyřmi chromatickými jednotkami, Golombův graf, byl objeven zhruba ve stejné době uživatelem Solomon W. Golomb.[2]
V roce 2018 počítačový vědec a biolog Aubrey de Gray našel 1581-vertex, non-4-barevný jednotkovou vzdálenost graf. Důkaz je podporován počítačem.[3] Matematik Gil Kalai[4] a počítačový vědec Scott Aaronson[5] zveřejnil diskusi o nálezu de Greyho, přičemž Aaronson hlásil nezávislé ověření výsledku de Greyho pomocí SAT řešitelé. Kalai propojil další příspěvky od uživatele Jordan Ellenberg a Noam Elkies, přičemž Elkies a (samostatně) de Gray navrhli a Polymath projekt najít non-4-colorable jednotkové vzdálenosti grafy s méně vrcholy než ten v de Grey konstrukci. Jak 2018, nejmenší známý graf s chromatickým číslem 5 měl 553 vrcholů Heule (2018), ale v srpnu 2019 našel Jaan Parts příklad 510 vrcholů.[6] Stránka projektu Polymath, Polymath (2018), obsahuje další výzkum, citace médií a ověřovací údaje.
Horní hranice sedmičky na chromatickém čísle vyplývá z existence a mozaikování roviny pravidelnými šestiúhelníky s průměrem o něco menším než jedna, kterým lze přiřadit sedm barev v opakujícím se vzoru a vytvořit tak 7-zbarvení roviny. Podle Soifer (2008), tato horní hranice byla poprvé pozorována u John R. Isbell.
Variace problému
Problém lze snadno rozšířit na vyšší rozměry. Zejména zjištění chromatického počtu prostoru se obvykle vztahuje k trojrozměrné verzi. Stejně jako u verze v letadle není odpověď známa, ale ukázalo se, že je minimálně 6 a maximálně 15.[7]
V n-dimenzionální případ problému, snadná horní hranice počtu požadovaných barev nalezených z obkladů n-dimenzionální kostky je . Dolní mez ze simplexů je . Pro , dolní mez je k dispozici pomocí zevšeobecnění Moserova vřetena: dvojice objektů (každý 2 simplexy slepené dohromady na ploše), které jsou spojeny na jedné straně bodem a druhé straně čarou.
Lze také zvážit zbarvení roviny, ve které jsou sady bodů každé barvy omezeny na sady určitého typu.[8] Taková omezení mohou způsobit zvýšení požadovaného počtu barev, protože zabrání tomu, aby byla určitá barviva považována za přijatelná. Například pokud zbarvení roviny sestává z oblastí ohraničených Jordan křivky, pak je vyžadováno alespoň šest barev.[9]
Viz také
Poznámky
- ^ Soifer (2008), str. 557–563; Shelah & Soifer (2003).
- ^ Soifer (2008), str. 19.
- ^ de Gray (2018).
- ^ Kalai (2018)
- ^ Aaronson (2018)
- ^ Komentář dílů k vláknu Polymath 16, 3. srpna 2019
- ^ Coulson (2002); Radoičić & Tóth (2003).
- ^ Viz např. Croft, Falconer & Guy (1991).
- ^ Woodall (1973); viz také Coulson (2004) pro jiný důkaz o podobném výsledku.
Reference
- Aaronson, Scott (11. dubna 2018), Úžasný pokrok v dlouhodobých otevřených problémech
- de Bruijn, N. G.; Erdős, P. (1951), „Barevný problém pro nekonečné grafy a problém v teorii vztahů“, Nederl. Akad. Wetensch. Proc. Ser. A, 54: 371–373, doi:10.1016 / S1385-7258 (51) 50053-7.
- Chilakamarri, K. B. (1993), „Problém grafu jednotkové vzdálenosti: krátký průzkum a některé nové výsledky“, Bull Inst. Kombinovat. Appl., 8: 39–60.
- Chilakamarri, Kiran B .; Mahoney, Carolyn R. (1996), „Graphs of unit-distance, graphs on the integer lattice and a Ramsey type result“, Aequationes Mathematicae, 51 (1–2): 48–67, doi:10.1007 / BF01831139, PAN 1372782.
- Coulson, D. (2004), „O chromatickém počtu naklonění roviny“, J. Austral. Matematika. Soc., 77 (2): 191–196, doi:10.1017 / S1446788700013574.
- Coulson, D. (2002), „15barevná 3prostorová vynechaná vzdálenost jedna“, Diskrétní matematika., 256 (1–2): 83–90, doi:10.1016 / S0012-365X (01) 00183-2.
- Croft, Hallard T .; Falconer, Kenneth J .; Guy, Richard K. (1991), Nevyřešené problémy v geometrii, Springer-Verlag, Problém G10.
- Gardner, Martin (1960), "Matematické hry", Scientific American, 203/4: 180.
- de Gray, Aubrey D.N.J. (2018), „Chromatický počet letadel je nejméně 5“, Geombinatorika, 28: 5–18, arXiv:1804.02385, Bibcode:2016arXiv160407134W.
- Hadwiger, Hugo (1945), „Überdeckung des euklidischen Raumes durch kongruente Mengen“, Portugalsko. Matematika., 4: 238–242.
- Hadwiger, Hugo (1961), „Ungelöste Probleme No. 40“, Elem. Matematika., 16: 103–104.
- Heule, Marijn J.H. (2018), Výpočet malých grafů na jednotku a vzdálenost s chromatickým číslem 5, arXiv:1805.12181, Bibcode:2018arXiv180512181H
- Jensen, Tommy R .; Toft, Bjarne (1995), Problémy s barvením grafů, Wiley-Interscience Series in Discrete Mathematics and Optimization, str. 150–152.
- Kalai, Gil (10. dubna 2018), Aubrey de Gray: Chromatické číslo letadla je alespoň 5
- Polymath, D. H. J. (Duben 2018), Hadwiger-Nelsonův problém (stránka projektu Polymath)
- Radoičić, Radoš; Tóth, Géza (2003), „Poznámka k chromatickému číslu prostoru“, Diskrétní a výpočetní geometrie: Goodman – Pollack Festschrift (PDF)Algoritmy a kombinatorika, 25, Berlín: Springer, str. 695–698, doi:10.1007/978-3-642-55566-4_32, PAN 2038498.
- Shelah, Saharon; Soifer, Alexander (2003), "Axiom volby a chromatické číslo roviny" (PDF), Journal of Combinatorial Theory, Series A, 103 (2): 387–391, doi:10.1016 / S0097-3165 (03) 00102-X, archivovány z originál (PDF) dne 14.06.2011.
- Soifer, Alexander (2008), Matematická omalovánka: Matematika zbarvení a barevný život jeho tvůrců, New York: Springer, ISBN 978-0-387-74640-1
- Woodall, D. R. (1973), „Vzdálenosti realizované soustavami pokrývajícími letadlo“, Journal of Combinatorial Theory, Řada A, 14 (2): 187–200, doi:10.1016/0097-3165(73)90020-4, PAN 0310770
externí odkazy
- O'Rourke, Josephe, „Problém 57: Chromatické číslo roviny“, Projekt Otevřené problémy, archivovány z originál dne 30. 8. 2006
- Mohar, Bojan (2001), Chromatické číslo grafu jednotkové vzdálenosti
- Kalai, Gil (2018), Problémy s barvením pro uspořádání kruhů (a pseudokruhů)
- Grime, James (27. února 2019), „Barevný nevyřešený problém“, Numberphile