Hrabě Schläfli

hrabě Schläfli
Vrcholy 27
žebra 216
Chromatické číslo 9
Vlastnosti Velmi pravidelné
Bez kleští
 Mediální soubory na Wikimedia Commons

V teorii grafů je Schläfliho graf 16 – pravidelný neorientovaný graf s 27 vrcholy a 216 hranami. Hrabě je pojmenován po Ludwigu Schläflim . Jedná se o silně pravidelný graf s parametry srg(27, 16, 10, 8).

Konstrukce

Průsečíkový graf 27 čar na krychlovém povrchu je doplňkem Schläfliho grafu. Dva vrcholy tedy sousedí v Schläfliho grafu právě tehdy, když jsou odpovídající čáry zešikmené [1]

Schläfliho graf lze získat také ze systému osmirozměrných vektorů

(1, 0, 0, 0, 0, 0, 1, 0), (1, 0, 0, 0, 0, 0, 0, 1) a (−1/2, −1/2, 1/2, 1/2, 1/2, 1/2, 1/2, 1/2),

a 24 vektorů získaných permutací prvních šesti souřadnic těchto tří vektorů. Těchto 27 vektorů odpovídá vrcholům Schläfliho grafu. Dva vrcholy jsou sousedící právě tehdy, když vnitřní součin odpovídajících dvou vektorů je 1 [2] .

Podgrafy a sousedství

Okolí jakéhokoli vrcholu Schläfliho grafu je 16-vrcholový podgraf, ve kterém má každý vrchol 10 sousedních vrcholů (čísla 16 a 10 se získají jako parametry Schläfliho grafu, když se s ním zachází jako s přísně regulárním grafem). Všechny tyto podgrafy jsou izomorfní s doplňkem Clebschova grafu [1] [3] . Protože Clebschův graf neobsahuje trojúhelníky , Schläfliho graf neobsahuje drápy . Tato skutečnost hraje důležitou roli v bezdrápové strukturní teorii grafů, kterou vyvinuli Maria Chudnovskaya a Paul Seymour [4] .

Jakékoli dvě protínající se čáry z těchto 27 čar patří do jediné Schläfli double-šest konfigurace ,  souboru 12 čar, jejichž průsečík tvoří korunu . V souladu s tím v Schläfliho grafu patří každá hrana uv do jediného podgrafu tvořeného přímým součinem úplných grafů K 6 K 2 , ve kterých vrcholy u a v patří do různých K 6 podgrafů součinu. Schläfliho graf obsahuje 36 podgrafů tohoto druhu, z nichž jeden se skládá z vektorů se souřadnicemi 0 a 1 v osmirozměrném prostoru, jak je popsáno výše [2] .

Ultrahomogenita

Graf se nazývá k -ultrahomogenní , pokud lze jakýkoli izomorfismus mezi dvěma jeho vygenerovanými podgrafy obsahujícími nejvýše k vrcholů rozšířit na automorfismus celého grafu. Pokud je graf 5-ultrahomogenní, pak je ultrahomogenní pro libovolné k . Jedinými připojenými konečnými grafy tohoto typu jsou kompletní grafy , Turanovy grafy , 3×3 věžové grafy a 5-vrcholový cyklus . Nekonečný Radův graf je spočetně ultrahomogenní. Existují pouze dva spojené grafy, které jsou 4-ultrahomogenní, ale ne 5-ultrahomogenní, Schläfliho graf a jeho doplněk. Důkaz je založen na klasifikaci jednoduchých konečných grup [5] [6] [7] .

Poznámky

  1. ↑ 1 2 D. A. Holton, J. Sheehan. Petersenův graf . - Cambridge University Press , 1993. - s . 270-271 .
  2. ↑ 1 2 F. C. Bussemaker, A. Neumaier. Výjimečné grafy s nejmenší vlastní hodnotou-2 a související problémy  // Matematika počítání. - 1992. - T. 59 , no. 200 _ — S. 583–608 . - doi : 10.1090/S0025-5718-1992-1134718-6 .
  3. ↑ Peter Jephson Cameron, Jacobus Hendricus van Lint. Designy, grafy, kódy a jejich odkazy. - Cambridge University Press, 1991. - V. 22 . - S. 35 . - ISBN 978-0-521-41325-1 . Je třeba poznamenat, že Cameron a van Lint použili jiné definice těchto grafů, podle nichž Schläfliho graf i Clebschův graf jsou doplňky zde definovaných grafů.
  4. ↑ Maria Chudnovsky, Paul Seymour. Průzkumy v kombinatorice 2005. - Cambridge Univ. Tisk, 2005. - T. 327 . — S. 153–171 . Archivováno z originálu 9. června 2010.
  5. ↑ JMJ Buczak. Teorie konečných grup. — Oxfordská univerzita, 1980.
  6. ↑ Peter Jephson Cameron. 6-tranzitivní grafy // Journal of Combinatorial Theory, Series B. - 1980. - T. 28 . — S. 168–179 .
  7. ↑ Alice Devillers. Klasifikace některých homogenních a ultrahomogenních struktur. — Université Libre de Bruxelles, 2002.

Odkazy