Earl of Hoffman-Singleton | |
---|---|
Döpt efter |
Alan Hoffman Robert R. Singleton |
Toppar | femtio |
revben | 175 |
Radie | 2 |
Diameter | 2 [1] |
Omkrets | 5 [1] |
Automorfismer |
252 000 ( PSU(3,5 2 ):2) [2] |
Kromatiskt nummer | fyra |
Kromatiskt index | 7 [3] |
Släkte | 29 [4] |
Egenskaper |
Starkt regelbunden symmetrisk Hamiltonian heltalsbur Moore -graf |
Mediafiler på Wikimedia Commons |
Hoffman-Singleton-grafen är en 7 - homogen oriktad graf med 50 hörn och 175 kanter. Grafen är den enda starkt regelbundna grafen med parametrar [5] . Grafen konstruerades av Alan Hoffman och Robert Singleton när de försökte klassificera alla Moore-grafer , och det är den högsta ordningens Moore-graf som en sådan graf är känd för att existera [6] . Eftersom grafen är en Moore-graf , där varje vertex har grad 7 och omkretsen på grafen är 5, är grafen en cell .
Det finns många sätt att konstruera Hoffman-Singleton-grafer.
Låt oss ta 5 pentagoner och 5 pentagram så att toppunkten på femhörningen gränsar till toppen av och femhörningen och pentagrammets vertex ligger intill toppen av och pentagrammet . Låt oss koppla samman toppen av grafen med toppen av grafen . (Alla index är tagna modulo 5.)
Ta ett Fano-plan och överväg att permutera dess 7 poäng för att få 30 Fano-plan. Låt oss välja ett av dessa plan. Det finns 14 andra Fano-plan som har exakt en gemensam trippel ("linje") med det valda planet. Ta dessa 15 Fano-plan och släng de återstående 15. Tänk på 7 C 3 = 35 trillingar med 7 siffror. Nu ansluter vi (med en kant) en trippel med Fano-planen som innehåller denna trippel, och kopplar även ihop icke-korsande trippel med varandra. Den resulterande grafen är en Hoffman-Singleton-graf, den består av 50 hörn som motsvarar 35 tripletter och 15 Fano-plan, och varje vertex har grad 7. De hörn som motsvarar Fano-planen är per definition kopplade till 7 tripletter, eftersom Fano-planet har 7 rader. Varje trippel är associerad med 3 olika Fano-plan som inkluderar den, och med 4 andra trippel som den inte korsar.
Automorfismgruppen i Hoffman-Singleton-grafen är en grupp av ordningen 252000 och är isomorf till PΣU(3,5 2 ), den halvdirekta produkten av den projektiva speciella enhetsgruppen och den cykliska gruppen av ordning 2 genererad av Frobenius-endomorfismen . En automorfism verkar transitivt på hörn och kanter av en graf. Hoffman-Singleton-grafen är således en symmetrisk graf . Grafens vertexstabilisator är isomorf till den symmetriska gruppen på 7 bokstäver. Kantsättningsstabilisatorn är isomorf till , där är en alternerande grupp på 6 bokstäver. Båda typerna av stabilisatorer är maximala undergrupper av hela automorfismgruppen i Hoffman-Singleton-grafen.
Det karakteristiska polynomet i Hoffman-Singleton-grafen är . Således är Hoffman-Singleton-grafen heltal - dess spektrum består helt av heltal.
Genom att bara använda det faktum att Hoffman-Singleton-grafen är strikt regelbunden med parametrar , kan vi visa att det finns 1260 cykler med längden 5 i den.
Dessutom innehåller Hoffman-Singleton Count 525 exemplar av Petersen Count . Att ta bort en av dem ger en kopia av den enda cellen [ 7] .