Hrabě z Hoffman-Singleton

hrabě z Hoffman-Singleton

Pojmenoval podle	Alan Hoffman Robert R. Singleton
Vrcholy	padesáti
žebra	175
Poloměr	2
Průměr	2 [1]
obvod	5 [1]
Automorfismy	252 000 ( PSU(3,5 2 ):2) [2]
Chromatické číslo	čtyři
Chromatický index	7 [3]
Rod	29 [4]
Vlastnosti	Silně pravidelné symetrické hamiltonovské celé číslo Cage Mooreův graf
Mediální soubory na Wikimedia Commons

Hoffman-Singletonův graf je 7 - homogenní neorientovaný graf s 50 vrcholy a 175 hranami. Graf je jediným silně regulárním grafem s parametry [5] . Graf zkonstruovali Alan Hoffman a Robert Singleton, když se pokoušeli klasifikovat všechny Mooreovy grafy , a je to Moorův graf nejvyššího řádu, o kterém je známo, že takový graf existuje [6] . Protože graf je Moorův graf , ve kterém má každý vrchol stupeň 7 a obvod grafu je 5, je grafem buňka . $(50,7,0,1)$ $(7,5)$

Konstrukce

Existuje mnoho způsobů, jak sestavit Hoffman-Singletonovy grafy.

Konstrukce založená na pětiúhelnících a pentagramech

Vezměme 5 pětiúhelníků a 5 pentagramů tak, aby vrchol pětiúhelníku sousedil s vrcholy a pětiúhelník a vrchol pentagramu sousedil s vrcholy a pentagram . Spojme horní část grafu s horní částí grafu . (Všechny indexy jsou brány modulo 5.) $P_{h}$ $Qi}$ $j$ $P_{h}$ $j-1$ $j+1$ $P_{h}$ $j$ $Qi}$ $j-2$ $j+2$ $Qi}$ $j$ $P_{h}$ $h\bullet {i}+j$ $Qi}$

Konstrukce z trojic a letadel Fano

Vezměte letadlo Fano a zvažte permutaci jeho 7 bodů, abyste získali 30 letadel Fano. Vyberme si jednu z těchto rovin. Existuje 14 dalších Fano rovin, které mají právě jednu společnou trojici ("linii") s vybranou rovinou. Vezměte těchto 15 Fano rovin a zbývajících 15 vyhoďte. Uvažujme 7 C 3 = 35 trojic 7 čísel. Nyní spojíme (hranou) trojici s rovinami Fano obsahující tuto trojici a také spojíme vzájemně neprotínající se trojice. Výsledný graf je Hoffmanův-Singletonův graf, skládá se z 50 vrcholů odpovídajících 35 tripletům a 15 Fano rovinám a každý vrchol má stupeň 7. Vrcholy odpovídající Fanovým rovinám jsou podle definice spojeny se 7 triplety, protože Fano rovina má 7 řádků. Každá trojice je spojena se 3 různými rovinami Fano, které ji zahrnují, a se 4 dalšími trojicemi, se kterými se nekříží.

Algebraické vlastnosti

Grupa automorfismu Hoffman-Singletonova grafu je grupa řádu 252 000 a je izomorfní k PΣU(3,5 2 ), polopřímému součinu projektivní speciální unitární grupy . $PSU(3,5^{2})$ a cyklická skupina řádu 2 vytvořená Frobeniovým endomorfismem . Automorfismus působí tranzitivně na vrcholy a hrany grafu. Hoffman-Singletonův graf je tedy symetrický graf . Vrcholový stabilizátor grafu je izomorfní k symetrické skupině na 7 písmenech. Stabilizátor sady hran je izomorfní k , kde je střídající se skupina 6 písmen. Oba typy stabilizátorů jsou maximálními podskupinami skupiny plného automorfismu Hoffman-Singletonova grafu. $S_7$ $Aut(A_{6})=A_{6}\cdot 2^{2}$ $A_{6}$

Charakteristickým polynomem Hoffman-Singletonova grafu je . Hoffman-Singletonův graf je tedy celočíselný – jeho spektrum se skládá výhradně z celých čísel. $(x-7)(x-2)^{28}(x+3)^{21}$

Podgrafy

Pouze na základě skutečnosti, že Hoffmanův-Singletonův graf je přísně regulární s parametry , můžeme ukázat, že v něm je 1260 cyklů délky 5. $(50,7,0,1)$

Kromě toho Hoffman-Singleton Count obsahuje 525 kopií Petersen Count . Odstraněním jednoho z nich získáte kopii jediné buňky [ 7] . $(6,5)$

Viz také

Tabulka největších známých grafů daného průměru a maximálního stupně

Poznámky

↑ 1 2 Weisstein, Eric W. Hoffman-Singleton Graph na webu Wolfram MathWorld .
↑ Hafner, 2003 , str. 7-12.
↑ Royle .
↑ Conder, Stokes, 2014 .
↑ Prohlížeč .
↑ Hoffman, Singleton, 1960 , str. 497–504.
↑ Wong, 1979 , s. 407–409.

Literatura

PR Hafner. Hoffmanův-Singletonův graf a jeho automorfismy // J. Algebraic Combin. - 2003. - T. 18 .
G. Royle. Re: Jaké je chromatické číslo hrany Hoffman-Singleton? . příspěvek na [email protected]. (28. září 2004.). (neurčitý) (nedostupný odkaz)
MDE Conder, K. Stokes. Minimální rodová vložení Hoffman-Singletonova grafu // předtisk. — 2014.
C. T. Benson, N. E. Losey. Na grafu Hoffmana a Singletona // Journal of Combinatorial Theory. Řada B. - svazek 11 , č. 1 . — S. 67–79 . — ISSN 0095-8956 . - doi : 10.1016/0095-8956(71)90015-3 .
D. A. Holton, J. Sheehan. Petersengraph . - Cambridge University Press , 1993. - S. 186 , 190. - ISBN 0-521-43594-3 . .
Andries E. Brouwer. Hoffman-Singletonův graf . Získáno 7. září 2016. Archivováno z originálu 3. března 2016. (neurčitý)
Alan J. Hoffman, Robert R. Singleton. Mooreovy grafy s průměrem 2 a 3 // IBM Journal of Research and Development. - 1960. - V. 5 , čís. 4 . — S. 497–504 . - doi : 10.1147/rd.45.0497 .
Pak-Ken Wong. O jedinečnosti nejmenšího grafu obvodu 5 a valence 6 // Journal of Graph Theory. - 1979. - T. 3 . — S. 407–409 . - doi : 10.1002/jgt.3190030413 .