Grev Schläfli

Grev Schläfli
Toppe 27
ribben 216
Kromatisk tal 9
Ejendomme Meget regelmæssig
Ingen tang
 Mediefiler på Wikimedia Commons

I grafteori er en Schläfli-graf en 16 - regulær urettet graf med 27 hjørner og 216 kanter. Greven er opkaldt efter Ludwig Schläfli . Dette er en meget regulær graf med parametrene srg(27, 16, 10, 8).

Konstruktion

Skæringsgrafen med 27 linjer på en kubisk overflade er komplementet til Schläfli-grafen. Således støder to hjørner til hinanden i en Schläfli-graf, hvis og kun hvis de tilsvarende linjer er skæve [1]

Schläfli-grafen kan også fås fra systemet af otte-dimensionelle vektorer

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

og 24 vektorer opnået ved at permutere de første seks koordinater af disse tre vektorer. Disse 27 vektorer svarer til hjørnerne af Schläfli-grafen. To hjørner er tilstødende, hvis og kun hvis det indre produkt af de tilsvarende to vektorer er 1 [2] .

Undergrafer og kvarterer

Nabolaget til et hvilket som helst toppunkt på en Schläfli-graf er en 16-vertex-undergraf, hvor hvert toppunkt har 10 nabospidser (tallene 16 og 10 opnås som parametre for Schläfli-grafen, når den behandles som en strengt regulær graf). Alle disse undergrafer er isomorfe i forhold til komplementet til Clebsch-grafen [1] [3] . Da Clebsch-grafen ikke indeholder trekanter , indeholder Schläfli-grafen ikke kløer . Dette faktum spiller en vigtig rolle i den klofrie strukturelle teori om grafer udviklet af Maria Chudnovskaya og Paul Seymour [4] .

Enhver to skærende linjer af disse 27 linjer tilhører den eneste Schläfli dobbelt-seks- konfiguration , et  sæt på 12 linjer, hvis skæringspunkt danner en krone . I Schläfli-grafen hører hver kant uv derfor til den eneste undergraf, der er dannet af det direkte produkt af de komplette grafer K 6 K 2 , hvor hjørnerne u og v tilhører forskellige K 6 - undergrafer af produktet. Schläfli-grafen indeholder 36 undergrafer af denne art, hvoraf den ene består af vektorer med koordinaterne 0 og 1 i det ottedimensionale rum, som beskrevet ovenfor [2] .

Ultrahomogenitet

En graf kaldes k -ultrahomogen hvis enhver isomorfi mellem to af dens genererede undergrafer, der indeholder højst k hjørner, kan udvides til en automorfi af hele grafen. Hvis en graf er 5-ultrahomogen, så er den ultrahomogen for enhver k . De eneste forbundne endelige grafer af denne type er komplette grafer , Turan-grafer , 3×3 - tårne-grafer og en 5-vertex- cyklus . Den uendelige Rado-graf er tælleligt ultrahomogen. Der er kun to forbundne grafer, der er 4-ultrahomogene, men ikke 5-ultrahomogene, Schläfli-grafen og dens komplement. Beviset er baseret på klassificeringen af ​​simple endelige grupper [5] [6] [7] .

Noter

  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. Ekstraordinære grafer med mindste egenværdi-2 og relaterede problemer  // Mathematics of Computation. - 1992. - T. 59 , no. 200 . — S. 583–608 . - doi : 10.1090/S0025-5718-1992-1134718-6 .
  3. ↑ Peter Jephson Cameron, Jacobus Hendricus van Lint. Designs, grafer, koder og deres links. - Cambridge University Press, 1991. - V. 22 . - S. 35 . - ISBN 978-0-521-41325-1 . Det skal bemærkes, at Cameron og van Lint brugte andre definitioner af disse grafer, ifølge hvilke både Schläfli-grafen og Clebsch-grafen er komplementer til de grafer, der er defineret her.
  4. ↑ Maria Chudnovsky, Paul Seymour. Undersøgelser i kombinatorik 2005. - Cambridge Univ. Presse, 2005. - T. 327 . — S. 153–171 . Arkiveret fra originalen den 9. juni 2010.
  5. ↑ JMJ Buczak. Finite Group Theory. — Oxford University, 1980.
  6. ↑ Peter Jephson Cameron. 6-transitive grafer // Journal of Combinatorial Theory, Series B. - 1980. - T. 28 . — S. 168–179 .
  7. ↑ Alice Devillers. Klassificering af nogle homogene og ultrahomogene strukturer. — Université Libre de Bruxelles, 2002.

Links