Jarl af Hoffman-Singleton

Jarl af Hoffman-Singleton

Opkaldt efter	Alan Hoffman Robert R. Singleton
Toppe	halvtreds
ribben	175
Radius	2
Diameter	2 [1]
Omkreds	5 [1]
Automorfismer	252.000 ( PSU(3,5 2 ):2) [2]
Kromatisk tal	fire
Kromatisk indeks	7 [3]
Slægt	29 [4]
Ejendomme	Stærkt regulær symmetrisk Hamiltonian Heltal Cage Moore Graph
Mediefiler på Wikimedia Commons

Hoffman-Singleton-grafen er en 7 - homogen urettet graf med 50 hjørner og 175 kanter. Grafen er den eneste stærkt regulære graf med parametre [5] . Grafen blev konstrueret af Alan Hoffman og Robert Singleton, da de forsøgte at klassificere alle Moore-grafer , og det er den højeste ordens Moore-graf, som en sådan graf er kendt for at eksistere [6] . Da grafen er en Moore-graf , hvor hvert toppunkt har grad 7, og omkredsen af grafen er 5, er grafen en celle . $(50,7,0,1)$ $(7,5)$

Konstruktion

Der er mange måder at konstruere Hoffman-Singleton-grafer på.

Konstruktion baseret på femkanter og pentagrammer

Lad os tage 5 femkanter og 5 femkanter , så toppunktet af femkanten støder op til toppunkterne på og femkanten og toppunktet på pentagrammet støder op til toppunkterne på og pentagrammet . Lad os forbinde toppen af grafen med toppen af grafen . (Alle indeks er taget 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 fra trillinger og Fano-fly

Tag et Fano-fly og overvej at permutere dets 7 point for at få 30 Fano-fly. Lad os vælge et af disse fly. Der er 14 andre Fano-fly, der har præcis én fælles tripel ("linje") med det valgte fly. Tag disse 15 Fano-fly og kasser de resterende 15. Overvej 7 C 3 = 35 trillinger af 7 tal. Nu forbinder vi (ved en kant) en tripel med Fano-planerne, der indeholder denne tripel, og forbinder også ikke-skærende tripler med hinanden. Den resulterende graf er en Hoffman-Singleton-graf, den består af 50 toppunkter svarende til 35 tripletter og 15 Fano-planer, og hvert toppunkt har grad 7. De toppunkter, der svarer til Fano-planerne, er per definition forbundet med 7 tripletter, da Fano-planet har 7 linjer. Hver triple er forbundet med 3 forskellige Fano-fly, der inkluderer den, og med 4 andre tripler, som den ikke krydser.

Algebraiske egenskaber

Automorfigruppen i Hoffman-Singleton-grafen er en gruppe af størrelsesordenen 252000 og er isomorf til PΣU(3,5 2 ), det halvdirekte produkt af den projektive specielle enhedsgruppe $PSU(3.5^{2})$ og den cykliske gruppe af orden 2 genereret af Frobenius endomorphism . En automorfi virker transitivt på spidserne og kanterne af en graf. Hoffman-Singleton-grafen er således en symmetrisk graf . Grafens toppunktstabilisator er isomorf i forhold til den symmetriske gruppe på 7 bogstaver. Kantsætstabilisatoren er isomorf til , hvor er en vekslende gruppe på 6 bogstaver. Begge typer stabilisatorer er maksimale undergrupper af den fulde automorfi-gruppe af Hoffman-Singleton-grafen. $S_7$ $Aut(A_{6})=A_{6}\cdot 2^{2}$ $A_{6}$

Det karakteristiske polynomium for Hoffman-Singleton-grafen er . Hoffman-Singleton-grafen er således heltal - dens spektrum består udelukkende af heltal. ${\displaystyle (x-7)(x-2)^{28}(x+3)^{21))$

Undergrafer

Ved kun at bruge det faktum, at Hoffman-Singleton-grafen er strengt regelmæssig med parametre , kan vi vise, at der er 1260 cyklusser med længde 5 i den. $(50,7,0,1)$

Desuden indeholder Hoffman-Singleton-greven 525 eksemplarer af Petersen-greven . Fjernelse af en af dem giver en kopi af den eneste celle [ 7] . $(6,5)$

Se også

Tabel over største kendte grafer med given diameter og maksimal grad

Noter

↑ 1 2 Weisstein, Eric W. Hoffman-Singleton Graph på Wolfram MathWorld -webstedet .
↑ Hafner, 2003 , s. 7-12.
↑ Royle .
↑ Conder, Stokes, 2014 .
↑ Brower .
↑ Hoffman, Singleton, 1960 , s. 497-504.
↑ Wong, 1979 , s. 407-409.

Litteratur

PR Hafner. Hoffman-Singleton-grafen og dens automorfismer // J. Algebraic Combin. - 2003. - T. 18 .
G. Royle. Re: Hvad er det Edge Chromatic Number for Hoffman-Singleton? . [email protected] opslag. (28. september 2004.). (ubestemt) (utilgængeligt link)
MDE Conder, K. Stokes. Minimum slægtsindlejringer af Hoffman-Singleton-grafen // fortryk. – 2014.
C.T. Benson, N.E. Losey. På en graf af Hoffman og 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 . Hentet 7. september 2016. Arkiveret fra originalen 3. marts 2016. (ubestemt)
Alan J. Hoffman, Robert R. Singleton. Moore-grafer med diameter 2 og 3 // IBM Journal of Research and Development. - 1960. - V. 5 , no. 4 . — S. 497–504 . - doi : 10.1147/rd.45.0497 .
Pak-Ken Wong. Om det unikke ved den mindste graf af omkreds 5 og valens 6 // Journal of Graph Theory. - 1979. - T. 3 . — S. 407–409 . - doi : 10.1002/jgt.3190030413 .