Moser vřeteno

Moserovo vřeteno ( Moser spindle , Moser graph ) je neorientovaný graf pojmenovaný po matematicích Leo Moserovi [en] a jeho bratru Williamovi, který má sedm vrcholů a jedenáct hran. Je to graf jednotkové vzdálenosti vyžadující čtyři barvy v jakémkoli zbarvení a jeho existence se používá k prokázání, že chromatické číslo letadla je alespoň čtyři.

Je také pojmenován po György Hajose , protože jej lze získat jako výsledek konstrukce Hajos [1] , nicméně název „graf Hajos“ se vztahuje i na jiné grafy, které vypadají jako trojúhelník vepsaný do šestiúhelníku. [2]

Konstrukce

Jako jednotkový graf vzdálenosti je Moserovo vřeteno tvořeno dvěma kosočtverci s úhly 60 a 120 stupňů, takže strany a krátké úhlopříčky kosočtverců tvoří rovnostranné trojúhelníky. Dva kosočtverce jsou umístěny v rovině tak, že dva vrcholy jejich ostrých úhlů se shodují a druhý pár vrcholů ostrých úhlů je umístěn ve vzdálenosti jednoty. Jedenáct hran grafu je osm hran kosočtverců, dvě krátké úhlopříčky a hrana mezi dvěma ostrými vrcholy kosočtverců.

Moserovo vřeteno může být konstruováno pouze v podmínkách teorie grafů, bez odkazu na geometrické vkládání, s konstrukcí Hayosh , počínaje dvěma úplnými grafy se čtyřmi vrcholy každý. Konstrukce odebere hranu z každého kompletního grafu, sloučí dva vrcholy odstraněných hran do jednoho vrcholu a přidá novou hranu spojující zbývající dva koncové vrcholy odstraněných hran. [3]

Dalším způsobem, jak sestrojit Moserovo vřeteno, je dokončit graf vytvořený z grafu rozdělením jedné z jeho hran. [čtyři]

Aplikace na problém Nelson-Erdős-Hadwiger

Nelson-Erdős-Hadwiger problém se ptá, kolik barev je potřeba k obarvení bodů euklidovské roviny takovým způsobem, že jakékoli dva body roviny, které leží v jednotkové vzdálenosti, jsou obarveny různými barvami. Ve skutečnosti jde o problém chromatického čísla nekonečného grafu, jehož vrcholy jsou všechny body roviny a hrany jsou všechny dvojice bodů ležících ve vzdálenosti jedné [5] .

Moserovo vřeteno vyžaduje čtyři barvy pro jakékoli zbarvení: pro jakékoli tříbarevné zbarvení budou mít ostré vrcholy kosočtverců stejnou barvu a pak hrana spojující dva ostré vrcholy kosočtverců spojí vrcholy stejné barvy. Tento rozpor ukazuje, že tři barvy nestačí a jsou vyžadovány alespoň čtyři barvy. Dostatek čtyř barev pro zbarvení Moserova vřetena vyplývá například i z toho, že jeho degenerace je tři.

Další důkaz toho, že k obarvení vřetena Moser jsou potřeba čtyři barvy, vyplývá z Hajoshovy konstrukce. Oba kompletní grafy, ze kterých je Moserovo vřeteno vytvořeno, vyžadují čtyři barvy a Hajoshova konstrukce tuto vlastnost zachovává [3] . Navíc každá nezávislá množina v Moserově vřetenu má maximálně dva vrcholy [6] , takže k pokrytí všech sedmi vrcholů jsou potřeba alespoň čtyři nezávislé množiny.

Protože Moserovo vřeteno je podgrafem grafu nekonečných jednotkových vzdáleností roviny, jsou k obarvení roviny potřeba alespoň čtyři barvy. Podle de Bruijn-Erdősovy věty (za předpokladu, že axiom výběru je pravdivý) se chromatické číslo roviny rovná maximálnímu chromatickému číslu všech konečných podgrafů. V roce 2018 Aubrey de Gray ukázal, že existuje graf jednotkové vzdálenosti, který vyžaduje k vybarvení alespoň 5 barev [7] . Nejlepší horní mez pro chromatické číslo roviny je sedm, což je mnohem více než počet barev potřebný k obarvení Moserova vřetena [5] .

Další vlastnosti a aplikace

Moserovo vřeteno je rovinné , což znamená, že jej lze kreslit v rovině bez průsečíků. Není však možné nakreslit vřeteno Moser tak, aby bylo rovinné a zároveň graf jednotkové vzdálenosti. To znamená, že to není shoda . Moserovo vřeteno je také lamanské , což znamená, že tvoří minimální tuhý systém , když je zasazeno do roviny. [8] Jako rovinný Lamanův graf je tento graf grafem s ostroúhlou pseudotrojúhelnatostí, což znamená, že jej lze zapustit do roviny takovým způsobem, že vnější plocha je konvexním trupem vložení a všemi vnitřními tváře jsou pseudotrojúhelníky s pouze třemi konvexními vrcholy. [9]

Doplněk Moserova grafu je graf bez trojúhelníku . Vložení Moserova grafu jako jednotkového grafu vzdálenosti tedy může být použito k vyřešení problému uspořádání sedmi bodů v rovině tak, že jakékoli tři body obsahují alespoň jeden pár, který je ve vzdálenosti jednoho. [5] [10]

Přidání libovolné hrany do Moserova vřetena bude mít za následek graf, který nelze vložit do roviny jako graf jednotkové vzdálenosti a neexistuje žádný homomorfismus Moserova vřetena k jakémukoli menšímu grafu jednotkové vzdálenosti. Tyto dvě vlastnosti Moserova vřetena byly použity v roce 2011 [11] , aby ukázaly, že kontrola grafu na existenci dvourozměrné reprezentace jako graf jednotkové vzdálenosti je NP-těžký problém. Důkaz využívá transformaci z 3SAT , ve které je Moserovo vřeteno použito jako řešič, který stanoví pravdivost vzorce. [osm]

Moserovo vřeteno lze také použít k prokázání výsledků v Ramseyho teorii pro euklidovskou rovinu - pokud je to trojúhelník v rovině a všechny body roviny jsou namalovány dvěma barvami (bílá a černá), pak buď existuje trojúhelník s černými vrcholy získanými z pohybu, nebo je pár bílých bodů ve vzdálenosti jedné. Pro důkaz používáme zapuštění vřetena Moser v rovině, ve kterém mají všechny hrany délku jedna. Dovolit  je součet Minkowského množiny a vrcholů trojúhelníku . Pokud ve vzdálenosti jedna v B nejsou žádné bílé body, pak každá ze tří kopií Moserova vřetena v B musí mít nejvýše dva bílé vrcholy, protože bílé vrcholy musí tvořit nezávislou množinu a maximální nezávislou množinu v Moseru vřeteno má velikost dvě. Mezi sedmi vrcholy Moserova vřetena tedy může mít nejvýše šest bílých vrcholů od , takže alespoň všechny kopie jednoho z vrcholů musí být černé. Takže tvoří trojúhelník, který je výsledkem pohybu. [6] [12]

Poznámky

1. ↑ Bondy & Murty, 2008 , str. 358.
2. ↑ Berge, 1989 , pp. 3-14.
3. ↑ 1 2 Hajos, 1961 , pp. 116-117.
4. ↑ Gervacio et al, 2008 , pp. 1973-1984.
5. ↑ 1 2 3 Soifer, 2008 , pp. 14-15.
6. ↑ 1 2 Burkert & Johnson, 2011 , pp. 97-113.
7. ↑ 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. (neurčitý)
8. ↑ 12 Horvat et al, 2011 , pp. 274-285.
9. ↑ Haas et al, 2005 , pp. 31-61.
10. ↑ Winkler, 2011 .
11. ↑ Horvat et al, 2011 .
12. ↑ Soifer, 2008 , Problém 40.26, str. 496.

Literatura

• Alexander Soifer. Matematická omalovánka: Matematika barvení a barevný život jejích tvůrců. — New York: Springer-Verlag New York, 2008. — 607 s. — ISBN 978-0387746401 .
• Jeffrey Burkert, Peter Johnson. Ramseyho teorie. - New York: Birkhäuser / Springer, 2011. - T. 285. - S. 97-113. - (Progr. Matematika).
• G. Hajos. Über eine Konstruktion nicht n -färbbarer Graphen. - 1961. - Sv. 10. - S. 116-117 .
• Boris Horvat, Jan Kratochvíl, Tomaž Pisanski. On the Computational Complexity of Degenerate Unit Distance Representations of Graphs // Combinatorial Algorithms: 21st International Workshop, IWOCA 2010, London, UK, July 26-28, 2010, Revised Selected Papers / Editors: Iliopoulos, Costas F., Smyth .. - Springer-Verlag Berlin Heidelberg, 2011. - Sv. 6460, str. 274-285. — 418 s. - (Teoretická informatika a obecné otázky). — ISBN 978-3-642-19222-7 . - doi : 10.1007/978-3-642-19222-7_28 . .
• Ruth Haas, David Orden, Günter Rote, Francisco Santos, Brigitte Servatius, Herman Servatius, Diane Souvaine, Ileana Streinu, Walter Whiteley. Rovinné minimálně tuhé grafy a pseudotriangulace // Teorie a aplikace výpočetní geometrie. - 2005. - T. 31 , no. 1–2 . - S. 31-61 . - doi : 10.1016/j.comgeo.2004.07.003 .
• Petr Winkler. Zmatený: Vzdálenosti mezi body v rovině // Komunikace ACM . - 2011. - Listopad ( díl 54 , číslo 11 ). - doi : 10.1145/2018396.2018422 .
• Severino V. Gervacio, Yvette F. Lim, Hiroshi Maehara. Grafy rovinné jednotky-vzdálenost s doplňkem rovinné jednotky-vzdálenost // Diskrétní matematika. - 2008. - T. 308 , č.p. 10 . - S. 1973-1984 . - doi : 10.1016/j.disc.2007.04.050 .
• Claude Berge. Minimax vztahy pro parciální q -zabarvení grafu // Diskrétní matematika . - 1989. - T. 74 , no. 1-2 . - str. 3-14 . - doi : 10.1016/0012-365X(89)90193-3 .
• JA Bondy, USR Murty. teorie grafů. - Springer, 2008. - T. 244 . - S. 358 . - doi : 10.1007/978-1-84628-970-5 .
• L. Moser, W. Moser. Řešení problému 10 // Can. Matematika. Bull .. - 1961. - T. 4 . - S. 187-189 .

Odkazy

• Weisstein, Eric W. Moser Spindle  (anglicky) na webových stránkách Wolfram MathWorld .