Hrabě Clebsha

hrabě Clebsha
Vrcholy 16
žebra 40
Poloměr 2
Průměr 2
obvod čtyři
Automorfismy 1920
Chromatické číslo 4 [1]
Vlastnosti Silně pravidelný
Hamiltonovský graf
Beztrojúhelníkový
graf Cayleyho graf
Vertexově tranzitivní
Hraně tranzitivní
Vzdálenostně tranzitivní
 Mediální soubory na Wikimedia Commons

V teorii grafů je Clebschův graf chápán jako jeden ze dvou komplementárních grafů s 16 vrcholy. Jeden z nich má 40 hran a je 5 - běžný graf , druhý má 80 hran a je to 10-běžný graf. Varianta s 80 hranami je graf poloviční krychle5. řádu. Seidelem pojmenován hrabě z Clebsche v roce 1968 [2] kvůli jeho souvislosti s konfigurací čar povrchu čtvrtého řádu, objeveným v roce 1868 německým matematikem Alfredem Clebschem . Varianta se 40 hranami je skládací krychlový graf5. řádu. Známý je také jako Greenwood-Gleasonův graf podle práce Greenwooda a Gleasona [3] , ve které tento graf použili k výpočtu Ramseyho čísla R (3,3,3) = 17 [3] [4] [5 ] .

Konstrukce

Graf skládací krychle5. řád (5-pravidelný Clebschův graf) lze sestrojit přidáním hran mezi protilehlé vrcholy 4-rozměrného hyperkrychlového grafu (V n - rozměrné hyperkrychli je dvojice vrcholů opačná, pokud nejkratší vzdálenost mezi nimi obsahuje n hran). Lze jej také sestavit z 5rozměrného grafu hyperkrychle stažením každého páru opačných vrcholů.

Další konstrukcí, která dává stejný graf, je vytvořit vrchol pro každý prvek konečného pole GF (16) a spojit dva vrcholy hranou, pokud je rozdíl odpovídajících prvků pole krychle [6] .

Graf půl kostky5. řád (10-běžný Clebschův graf) je doplňkem 5-pravidelného grafu. Lze jej také postavit z vrcholů 5-rozměrné hyperkrychle spojením dvojic vrcholů, mezi nimiž jsou Hammingova vzdálenost přesně dvě. Tato konstrukce tvoří dvě podmnožiny po 16 vrcholech, které nejsou vzájemně propojeny. Oba získané grafy jsou izomorfní s 10-regulárním Clebschovým grafem.

Vlastnosti

5-pravidelný Clebschův graf je silně pravidelný graf 5. stupně s parametry [7] [8] . Jeho doplněk, 10-pravidelný Clebschův graf, je také silně pravidelný [1] [5] .

5-pravidelný Clebschův graf je hamiltonovský , neplanární a neeulerovský . Oba grafy jsou spojeny 5 vrcholy a 5 hranami . Podgraf vytvořený deseti vrcholy, které nejsou sousedy žádného vrcholu v tomto grafu, je izomorfní s Petersenovým grafem .

Okraje kompletního grafu K 16 lze rozdělit na tři oddělené kopie 5-pravidelného Clebschova grafu. Protože Clebschův graf neobsahuje trojúhelníky , ukazuje to, že existuje trikolorní zbarvení bez trojúhelníků hran grafu K 16 . Ramseyho číslo R (3,3,3), které popisuje minimální počet vrcholů v kompletním grafu pod trikolorním zbarvením bez trojúhelníků, tedy nemůže být menší než 17. Greenwood a Gleason použili tuto konstrukci jako součást svého důkazu rovnost R (3,3, 3) = 17 [3] [9] .

5-běžný Clebschův graf je Kellerův graf dimenze dvě a patří do rodiny grafů používaných k nalezení pokrytí vysokorozměrných euklidovských prostorů hyperkrychlemi , které nemají společné plochy.

Algebraické vlastnosti

Charakteristickým polynomem 5-pravidelného Clebschova grafu je . Clebschův graf je tedy celočíselný graf – jeho spektrum se skládá výhradně z celých čísel [5] . Clebschův graf je jediný graf s tak charakteristickým polynomem.

5-pravidelný Clebschův graf je Cayleyův graf se skupinou automorfismu řádu 1920 izomorfní s Coxeterovou grupou . Jako v každém Cayleyově grafu působí skupina automorfismu na své vrcholy tranzitivně, takže je vertex-tranzitivní . Ve skutečnosti se jedná o symetrický graf , a proto je přechodově přechodný na hranu a přechod na vzdálenost .

Galerie

Poznámky

  1. 1 2 . Eric W. Weisstein. Clebschův graf. . Od MathWorld - Wolfram webový zdroj. Získáno 13. srpna 2009. Archivováno z originálu dne 7. února 2009.
  2. JJ Seidel, Silně pravidelné grafy s (−1,1,0) maticí sousednosti s vlastní hodnotou 3, Lin. Alg. Appl. 1 (1968) 281-298.
  3. 1 2 3 R. E. Greenwood, Andrew Gleason. Kombinatorické vztahy a chromatické grafy  // Canadian Journal of Mathematics. - 1955. - T. 7 . - S. 1-7 . - doi : 10.4153/CJM-1955-001-4 .
  4. A. Clebsch. Ueber die Flächen vierter Ordnung, welche eine Doppelcurve zweiten Grades besitzen // J. fur Math. - 1868. - T. 69 . - S. 142-184 .
  5. 1 2 3 The Clebsch Graph na domovské stránce Billa Cherowitza . Získáno 25. října 2013. Archivováno z originálu 29. října 2013.
  6. De Clerck, Frank Konstrukce a charakterizace (semi)parciálních geometrií . Letní škola konečných geometrií 6 (1997). Získáno 25. října 2013. Archivováno z originálu 15. června 2011.
  7. Problémy algebraické kombinatoriky // Electronic Journal of Combinatorics . - 1995. - T. 2 . - S. 3 .
  8. Peter J. Cameron Silně pravidelné grafy Archivováno 29. října 2013 na Wayback Machine na DesignTheory.org, 2001
  9. Hugo S. Sun, M. E. Cohen. Snadný důkaz Greenwood-Gleasonova hodnocení Ramseyho čísla R (3,3,3) // The Fibonacci Quarterly. - 1984. - T. 22 , no. 3 . - S. 235-238 .