Moser vřeteno

Moser vřeteno
Pojmenoval podle Leo Moser , William Moser
Vrcholy 7
žebra jedenáct
Poloměr 2
Průměr 2
obvod 3
Automorfismy osm
Chromatické číslo čtyři
Chromatický index čtyři
Vlastnosti planární laman
unit distance
graf

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.
  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

Odkazy