Grefve Schläfli

Grefve Schläfli
Toppar 27
revben 216
Kromatiskt nummer 9
Egenskaper Väldigt regelbunden
Ingen tång
 Mediafiler på Wikimedia Commons

I grafteorin är en Schläfli-graf en 16 - vanlig oriktad graf med 27 hörn och 216 kanter. Greven är uppkallad efter Ludwig Schläfli . Detta är en mycket regelbunden graf med parametrarna srg(27, 16, 10, 8).

Konstruktion

Skärningsgrafen med 27 linjer på en kubisk yta är komplementet till Schläfli-grafen. Således ligger två hörn intill i en Schläfli-graf om och endast om motsvarande linjer är skeva [1]

Schläfli-grafen kan också erhållas från systemet med åttadimensionella vektorer

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

och 24 vektorer erhållna genom att permutera de första sex koordinaterna för dessa tre vektorer. Dessa 27 vektorer motsvarar hörnen på Schläfli-grafen. Två hörn är angränsande om och endast om den inre produkten av motsvarande två vektorer är 1 [2] .

Subgrafer och stadsdelar

Närheten till valfri vertex i en Schläfli-graf är en subgraf med 16 vertex där varje vertex har 10 angränsande hörn (siffrorna 16 och 10 erhålls som parametrar för Schläfli-grafen när den behandlas som en strikt regelbunden graf). Alla dessa subgrafer är isomorfa till komplementet till Clebsch-grafen [1] [3] . Eftersom Clebsch-grafen inte innehåller trianglar , innehåller Schläfli-grafen inte klor . Detta faktum spelar en viktig roll i den klofria strukturteorin för grafer som utvecklats av Maria Chudnovskaya och Paul Seymour [4] .

Alla två korsande linjer av dessa 27 linjer tillhör den enda Schläfli dubbel-sex- konfigurationen , en  uppsättning av 12 linjer vars skärning bildar en krona . Följaktligen, i Schläfli-grafen, tillhör varje kant uv den enda subgraf som bildas av den direkta produkten av de kompletta graferna K 6 K 2 där hörnen u och v tillhör olika K 6 -subgrafer av produkten. Schläfli-grafen innehåller 36 subgrafer av detta slag, varav en består av vektorer med koordinaterna 0 och 1 i åttadimensionell rymd, som beskrivits ovan [2] .

Ultrahomogenitet

En graf kallas k -ultrahomogen om någon isomorfism mellan två av dess genererade subgrafer som innehåller högst k hörn kan utökas till en automorfism av hela grafen. Om en graf är 5-ultrahomogen så är den ultrahomogen för vilken k som helst . De enda anslutna finita graferna av denna typ är kompletta grafer , Turan-grafer , 3×3 torngrafer och en 5-vertexcykel . Den oändliga Rado-grafen är uträkneligt ultrahomogen. Det finns bara två sammankopplade grafer som är 4-ultrahomogena men inte 5-ultrahomogena, Schläfli-grafen och dess komplement. Beviset är baserat på klassificeringen av enkla ändliga grupper [5] [6] [7] .

Anteckningar

  1. ↑ 1 2 D. A. Holton, J. Sheehan. Petersen-grafen . - Cambridge University Press , 1993. - s . 270-271 .
  2. ↑ 1 2 F. C. Bussemaker, A. Neumaier. Exceptionella grafer med minsta egenvärde-2 och relaterade problem  // Mathematics of Computation. - 1992. - T. 59 , nr. 200 . — S. 583–608 . - doi : 10.1090/S0025-5718-1992-1134718-6 .
  3. ↑ Peter Jephson Cameron, Jacobus Hendricus van Lint. Design, grafer, koder och deras länkar. - Cambridge University Press, 1991. - V. 22 . - S. 35 . - ISBN 978-0-521-41325-1 . Det bör noteras att Cameron och van Lint använde andra definitioner av dessa grafer, enligt vilka både Schläfli-grafen och Clebsch-grafen är komplement till de grafer som definieras här.
  4. ↑ Maria Chudnovsky, Paul Seymour. Undersökningar i kombinatorik 2005. - Cambridge Univ. Press, 2005. - T. 327 . — S. 153–171 . Arkiverad från originalet den 9 juni 2010.
  5. ↑ JMJ Buczak. Finita gruppteori. — Oxford University, 1980.
  6. ↑ Peter Jephson Cameron. 6-transitiva grafer // Journal of Combinatorial Theory, Series B. - 1980. - T. 28 . — S. 168–179 .
  7. ↑ Alice Devillers. Klassificering av några homogena och ultrahomogena strukturer. — Université Libre de Bruxelles, 2002.

Länkar