Grev Clebsha

Grev Clebsha
Toppe 16
ribben 40
Radius 2
Diameter 2
Omkreds fire
Automorfismer 1920
Kromatisk tal 4 [1]
Ejendomme Stærkt regelmæssig
Hamiltonsk graf
Trekantfri
graf Cayley-graf
Vertex-transitiv
Kant-transitiv
Afstand-transitiv
 Mediefiler på Wikimedia Commons

I grafteori forstås en Clebsch-graf som en af ​​to komplementære grafer med 16 hjørner. En af dem har 40 kanter og er en 5 -regulær graf , den anden har 80 kanter og er en 10-regulær graf. Den 80-kantede variant er en halv kubegraf5. orden. Udnævnt til greve af Clebsch i 1968 af Seidel [2] på grund af dens forbindelse med konfigurationen af ​​linjer af den fjerde ordens overflade, opdaget i 1868 af den tyske matematiker Alfred Clebsch . Den 40-kantede variant er en foldbar kubegraf5. orden. Den er også kendt som Greenwood-Gleason grafen efter arbejdet fra Greenwood og Gleason [3] , hvor de brugte denne graf til at beregne Ramsey-tallet R (3,3,3) = 17 [3] [4] [5 ] .

Konstruktion

Foldende terninggraf5. orden (5-regulær Clebsch-graf) kan konstrueres ved at tilføje kanter mellem modsatte hjørner af en 4-dimensionel hyperkubegraf (I en n - dimensional hyperkube er et par hjørner modsat, hvis den korteste afstand mellem dem indeholder n kanter). Den kan også konstrueres ud fra en 5-dimensionel hyperkubegraf ved at kontrahere hvert par af modsatte hjørner.

En anden konstruktion, der giver den samme graf, er at skabe et toppunkt for hvert element i det endelige felt GF (16) og forbinde to toppunkter med en kant, hvis forskellen på de tilsvarende elementer i feltet er en terning [6] .

Halv kube graf5. orden (10-regulær Clebsch-graf) er komplementet til en 5-regulær graf. Det kan også bygges ud fra hjørnerne af en 5-dimensionel hyperkube ved at forbinde par af hjørner, mellem hvilke Hamming-afstanden er præcis to. Denne konstruktion danner to delmængder af hver 16 toppunkter, der ikke er forbundet med hinanden. Begge opnåede grafer er isomorfe i forhold til den 10-regulære Clebsch-graf.

Egenskaber

En 5-regulær Clebsch-graf er en stærkt regulær 5. gradsgraf med parametre [7] [8] . Dens komplement, den 10-regulære Clebsch-graf, er også meget regelmæssig [1] [5] .

Den 5-regulære Clebsch-graf er Hamiltonsk , ikke- plan og ikke-Eulerian . Begge grafer er 5 -vertex-forbundne og 5 -kant-forbundne . En undergraf genereret af ti spidser, der ikke er naboer til noget knudepunkt i denne graf, er isomorf med Petersen-grafen .

Kanterne af den komplette graf K 16 kan opdeles i tre adskilte kopier af den 5-regulære Clebsch-graf. Da Clebsch-grafen ikke indeholder trekanter , viser dette, at der er en trefarvet farvning uden trekanter af grafens kanter K 16 . Ramsey-tallet R (3,3,3) , som beskriver minimumsantallet af hjørner i en komplet graf under trefarvefarvning uden trekanter, kan således ikke være mindre end 17. Greenwood og Gleason brugte denne konstruktion som en del af deres bevis på lighed R (3,3, 3) = 17 [3] [9] .

Den 5-regulære Clebsch- graf er en Keller-graf af dimension to og tilhører en familie af grafer, der bruges til at finde dækningen af ​​højdimensionelle euklidiske rum af hyperkuber , der ikke har fælles flader.

Algebraiske egenskaber

Det karakteristiske polynomium for en 5-regulær Clebsch-graf er . Clebsch-grafen er således en heltalsgraf - dens spektrum består udelukkende af heltal [5] . Clebsch-grafen er den eneste graf med et så karakteristisk polynomium.

Den 5-regulære Clebsch- graf er en Cayley-graf med en automorfigruppe fra 1920, som er isomorf med Coxeter-gruppen . Som i enhver Cayley-graf, virker automorfigruppen transitivt på sine hjørner, hvilket gør den vertex-transitiv . Faktisk er det en symmetrisk graf , og derfor er den kanttransitiv og afstandstransitiv .

Galleri

Noter

  1. ↑ 1 2 . Eric W. Weisstein. Clebsch graf. . Fra MathWorld - En Wolfram-webressource. Hentet 13. august 2009. Arkiveret fra originalen 7. februar 2009.
  2. ↑ JJ Seidel, Stærkt regelmæssige grafer med (−1,1,0) tilstødende matrix med egenværdi 3, Lin. Alg. Appl. 1 (1968) 281-298.
  3. ↑ 1 2 3 R. E. Greenwood, Andrew Gleason. Kombinatoriske relationer og kromatiske grafer  // 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 på Bill Cherowitzos hjemmeside . Hentet 25. oktober 2013. Arkiveret fra originalen 29. oktober 2013.
  6. ↑ De Clerck, Frank Konstruktioner og karakteriseringer af (semi)partielle geometrier . Summer School on Finite Geometries 6 (1997). Hentet 25. oktober 2013. Arkiveret fra originalen 15. juni 2011.
  7. ↑ Problemer i algebraisk kombinatorik // Electronic Journal of Combinatorics . - 1995. - T. 2 . - S. 3 .
  8. ↑ Peter J. Cameron Stærkt regelmæssige grafer Arkiveret 29. oktober 2013 på Wayback Machine på DesignTheory.org, 2001
  9. ↑ Hugo S. Sun, M.E. Cohen. Et let bevis på Greenwood-Gleason-evalueringen af ​​Ramsey-nummeret R (3,3,3) // The Fibonacci Quarterly. - 1984. - T. 22 , no. 3 . - S. 235-238 .