Hoffman–Singleton-graf

Hoffman–Singleton-graf
Döpt efter	Alan J. Hoffman Robert R. Singleton
Vertices	50
Kanter	175
Radie	2
Diameter	2
Omkrets	5
Automorfismer	252 000 ( PSU (3,5 2 ):2)
Kromatiskt nummer	4
Kromatiskt index	7
Släkte	29
Egenskaper	Starkt regelbunden symmetrisk Hamiltonian Integral Cage Moore-graf
Tabell över grafer och parametrar

Hoffman–Singleton-grafen. Subgrafen av blå kanter är en summa av tio disjunkta femhörningar.

Inom det matematiska området grafteorin är Hoffman –Singleton-grafen en 7- regelbunden oriktad graf med 50 hörn och 175 kanter. Det är den unika, starkt regelbundna grafen med parametrar (50,7,0,1). Den konstruerades av Alan Hoffman och Robert Singleton medan de försökte klassificera alla Moore-grafer , och är den högsta ordningens Moore-graf som man vet finns. Eftersom det är en Moore-graf där varje vertex har grad 7, och omkretsen är 5, är det en (7,5) -bur .

Konstruktion

Här är två konstruktioner av Hoffman–Singleton-grafen.

Konstruktion från pentagoner och pentagram

Ta fem pentagoner P _h och fem pentagram Q _i . Sammanfoga vertex j av P _h till vertex h · i + j av Q _i . (Alla index är modulo 5.)

Konstruktion från PG(3,2)

Ta ett Fano-plan på sju element, som { abc, ade, afg, bef, bdg, cdf, ceg } och tillämpa alla 2520 jämna permutationer på 7-set abcdefg . Kanonisera varje sådant Fano-plan (t.ex. genom att reducera till lexikografisk ordning) och kassera dubbletter. Exakt 15 Fano-plan återstår. Varje 3-set (triplett) av setet abcdefg finns i exakt 3 Fano-plan. Incidensen mellan de 35 tripletterna och 15 Fano-planen inducerar PG(3,2) , med 15 punkter och 35 linjer. För att göra Hoffman-Singleton-grafen, skapa en grafvertex för vart och ett av de 15 Fano-planen och 35 trillingarna. Anslut varje Fano-plan till dess 7 tripletter, som en Levi-graf , och koppla även disjunkta tripletter till varandra som den udda grafen O(4).

En mycket liknande konstruktion från PG(3,2) används för att bygga Higman–Sims-grafen , som har Hoffman-Singleton-grafen som en subgraf.

Ett algebraiskt uttryck på en rad av Hoffman-Singleton-grafen är som följer:

Konstruktion på en groupoid

Låt $G$ vara mängden $\mathbb {Z} _{2}\times \mathbb {Z} _{5}\times \mathbb {Z} _{ 5}$ . Definiera en binär operation $\circ$ på $G$ enligt följande. För varje $(a,b,c)$ och $(x,y,z)$ i $G$ , $(a,b,c)\ circ (x,y,z)=(a+x,b-bx+y,c+(-1)^{a}by+2^{a}z)$ . Grafen vars hörn är $g\in G$ och att det finns en kant mellan $g$ och $g'\in G$ när $g'=g\circ s$ för vissa $s\in \{(0,0,1),(0,0,4),(1,0,0),(1,1,0 ),(1,2,0),(1,3,0),(1,4,0)\}$ är Hoffman-Singleton-grafen.

Algebraiska egenskaper

Automorfismgruppen i Hoffman–Singleton-grafen är en grupp av ordningen 252 000 isomorf till PΣU(3,5 ² ) den halvdirekta produkten av den projektiva speciella enhetsgruppen PSU(3,5 ² ) med den cykliska gruppen av ordning 2 genererad av Frobenius automorfism . Den verkar transitivt på hörnen, på kanterna och på grafens bågar. Därför är Hoffman–Singleton-grafen en symmetrisk graf . Stabilisatorn för en vertex av grafen är isomorf till den symmetriska gruppen S ₇ på 7 bokstäver. Den setvisa stabilisatorn för en kant är isomorf till Aut(A ₆ )=A ₆ .2 ² , där A ₆ är den alternerande gruppen på 6 bokstäver. Båda de två typerna av stabilisatorer är maximala undergrupper av hela automorfismgruppen i Hoffman-Singleton-grafen.

Det karakteristiska polynomet i Hoffman–Singleton-grafen är lika med $(x-7)(x-2)^{28}(x+3) )^{21}$ . Därför är Hoffman–Singleton-grafen en integrerad graf : dess spektrum består helt av heltal.

Hoffman-Singleton-grafen har exakt 100 oberoende uppsättningar av storlek 15 vardera. Varje oberoende uppsättning är skild från exakt 7 andra oberoende uppsättningar. Grafen med 100 vertex som förbinder osammanhängande oberoende uppsättningar kan delas upp i två subgrafer med 50 vertex, som var och en är isomorfisk mot Hoffman-Singleton-grafen, i ett ovanligt fall av självreplikerande + multiplicerande beteende.

Subgrafer och supergrafer

Det finns 1260 5-cykler och 5250 6-cykler i Hoffman–Singleton-grafen. Det finns 525 kopior av Petersen-grafen , där varje 6-cykel tillhör exakt en Petersen vardera. Att ta bort någon av Petersen lämnar en kopia av den unika (6,5) buren .

Hoffman–Singleton-grafen innehåller också många kopior av Möbius–Kantor-grafen och Heawood-grafen , som alla är tvådelade, och genom att färga dem med alternerande värden på +1 och -1 kan en egenvektor till grafen hittas, med tillhörande egenvärde på −3. (Detta är det enda negativa egenvärdet för Hoffman-Singleton-grafen.) Tillsammans spänner dessa egenvektorer över −3-egenutrymmet i Hoffman-Singleton-grafen, även om de utgör en mycket överkomplett grund: det finns många fler Möbius-Kantor-grafer eller Heawood - grafer än det finns −3 egenvektorer. Det finns 750 kopior av Heawood-grafen, och Heawood-grafen har automorfismgrupp av ordningen 336. I sin tur är 750*336 = 252000, storleken på automorfismgruppen i Hoffman-Singleton-grafen, vilket betyder att Hoffman-Singleton-grafen fixas genom att fixera vilken Heawood-graf som helst inuti den. På liknande sätt finns det 2625 kopior av Möbius–Kantor-grafen, som har automorfismgruppsordning 96, och 2625*96=252000, så det analoga uttalandet gäller.

Heawood-grafen är särskilt infallsgrafen för Fano-planet , och så efter 15+35-konstruktionen av Hoffman–Singleton-grafen ovan visar detta omedelbart många platser där Heawood-grafer måste förekomma. Ta en oberoende uppsättning av storlek 15 i Hoffman Singleton-grafen. Det finns 100 av dessa. Hitta en annan oberoende uppsättning som har 8 hörn gemensamt med den första. Det finns 15 sådana närliggande oberoende uppsättningar. Släng de 8 vanliga hörnen. De 14 hörn som finns kvar bildar en Heawood-graf. Det finns alltså 100*15/2 = 750 Heawood-grafer som fastställts tidigare.

Hoffman Singleton-grafen innehåller också den udda grafen O(4), Coxeter-grafen och Tutte-Coxeter-grafen som subgrafer.

Ta valfri kant på Hoffman-Singleton-grafen och kassera dessa två hörn såväl som de 12 hörnen som är direkt kopplade till någon av dem. Grafen som finns kvar är Sylvester-grafen på 36 hörn. Eftersom varje sådan kant kan mappas till en distinkt Sylvester-graf, finns det 175 kopior av Sylvester-grafen i Hoffman Singleton-grafen.

Hoffman Singleton-grafen finns i Higman-Sims-grafen som därför är en supergraf.

Se även

• McKay–Miller–Širáň-grafer , en klass av grafer inklusive Hoffman–Singleton-grafen
• Tabell över de största kända graferna för en given diameter och maximal grad

Anteckningar

•    Benson, CT; Losey, NE (1971), "On a graph of Hoffman and Singleton", Journal of Combinatorial Theory, Series B , 11 (1): 67–79, doi : 10.1016/0095-8956(71)90015-3 , ISSN 0095 -8956 , MR 0281658
• Chishwashwa, N.; Faber, V.; Streib, N. (2022), "Digraph Networks and Groupoids", arXiv : 2208.10537 [ math.CO ]
•   Holton, DA; Sheehan, J. (1993), The Petersen graph , Cambridge University Press , s. 186 och 190, ISBN 0-521-43594-3 .