Earl of Hoffman-Singleton

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 . $(50,7,0,1)$ $(7,5)$

Byggnad

Det finns många sätt att konstruera Hoffman-Singleton-grafer.

Konstruktion baserad på pentagoner och pentagram

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.) $P_{h}$ $Q_{i}$ $j$ $P_{h}$ $j-1$ $j+1$ $P_{h}$ $j$ $Q_{i}$ $j-2$ $j+2$ $Q_{i}$ $j$ $P_{h}$ $h\bullet {i}+j$ $Q_{i}$

Konstruktion från trillingar och Fano-plan

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.

Algebraiska egenskaper

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 $PSU(3.5^{2})$ 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. $S_7$ $Aut(A_{6})=A_{6}\cdot 2^{2}$ $A_{6}$

Det karakteristiska polynomet i Hoffman-Singleton-grafen är . Således är Hoffman-Singleton-grafen heltal - dess spektrum består helt av heltal. $(x-7)(x-2)^{28}(x+3)^{21}$

Subgrafer

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. $(50,7,0,1)$

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] . $(6,5)$

Se även

Tabell över största kända grafer med given diameter och maximal grad

Anteckningar

↑ 1 2 Weisstein, Eric W. Hoffman-Singleton Graph på Wolfram MathWorld -webbplatsen .
↑ Hafner, 2003 , sid. 7-12.
↑ Royle .
↑ Conder, Stokes, 2014 .
↑ Webbläsare .
↑ Hoffman, Singleton, 1960 , sid. 497–504.
↑ Wong, 1979 , sid. 407–409.

Litteratur

PR Hafner. Hoffman-Singleton-grafen och dess automorfismer // J. Algebraic Combin. - 2003. - T. 18 .
G. Royle. Re: Vad är Edge Chromatic Number för Hoffman-Singleton? . [email protected] inlägg. (28 september 2004.). (obestämd) (inte tillgänglig länk)
MDE Conder, K. Stokes. Minsta genusinbäddningar av Hoffman-Singleton-grafen // förtryck. — 2014.
C.T. Benson, N.E. Losey. På en graf över Hoffman och Singleton // Journal of Combinatorial Theory. Serie B. - Vol. 11 , nr. 1 . — S. 67–79 . — ISSN 0095-8956 . - doi : 10.1016/0095-8956(71)90015-3 .
D.A. Holton, J. Sheehan. Petersengrafen . - Cambridge University Press , 1993. - S. 186 , 190. - ISBN 0-521-43594-3 . .
Andries E. Brouwer. Hoffman-Singleton graf . Hämtad 7 september 2016. Arkiverad från originalet 3 mars 2016. (obestämd)
Alan J. Hoffman, Robert R. Singleton. Moore grafer med diameter 2 och 3 // IBM Journal of Research and Development. - 1960. - V. 5 , nr. 4 . — S. 497–504 . - doi : 10.1147/rd.45.0497 .
Pak-Ken Wong. Om det unika med den minsta grafen av omkrets 5 och valens 6 // Journal of Graph Theory. - 1979. - T. 3 . — S. 407–409 . - doi : 10.1002/jgt.3190030413 .