Hoffman – Singletonův graf - Hoffman–Singleton graph - Wikipedia

Hoffman – Singletonův graf
Pojmenoval podle	Alan J. Hoffman Robert R. Singleton
Vrcholy	50
Hrany	175
Poloměr	2
Průměr	2[1]
Obvod	5[1]
Automorfismy	252,000 (PSU (3,52):2)[2]
Chromatické číslo	4
Chromatický index	7[3]
Rod	29[4]
Vlastnosti	Silně pravidelné Symetrický Hamiltonian Integrální Klec Mooreův graf
Tabulka grafů a parametrů

Hoffman-Singletonův graf. Podgraf modrých hran je součtem deseti disjunktních pětiúhelníků.

V matematický pole teorie grafů, Hoffman – Singletonův graf je 7-pravidelný neorientovaný graf s 50 vrcholy a 175 hranami. Je to jedinečný silně pravidelný graf s parametry (50,7,0,1).^[5] To bylo postaveno Alan Hoffman a Robert Singleton, zatímco se snaží klasifikovat vše Mooreovy grafy a je to Mooreův graf nejvyššího řádu, o kterém je známo, že existuje.^[6] Protože se jedná o Mooreův graf kde každý vrchol má stupeň 7 a obvod je 5, je to (7,5) -klec.

Konstrukce

Zde jsou dvě konstrukce grafu Hoffman – Singleton.^[7]

Konstrukce z pětiúhelníků a pentagramů

Dát si pauzu pětiúhelníky P_h a pět pentagramy Q_i . Připojte se k vrcholu j z P_h na vrchol h·i+j z Q_i. (Všechny indexy jsou modulo 5.)^[7]

Stavba z PG (3,2)

Vezměte si Fano letadlo na sedmi prvcích, jako je {abc, ade, afg, bef, bdg, cdf, ceg} a použít všech 2520 dokonce i obměny na 7-set abcdefg. Kanonikujte každé takové Fano letadlo (např. Redukcí na lexikografické pořadí) a zahoďte duplikáty. Přesně 15 Fano letadel zůstává. Každá 3 sada (triplet) sady abcdefg je přítomen přesně ve 3 rovinách Fano. Incidence mezi 35 triplety a 15 Fano letadly indukuje PG (3,2), s 15 body a 35 řádky. Chcete-li vytvořit Hoffman-Singletonův graf, vytvořte vrchol grafu pro každou z 15 Fano rovin a 35 tripletů. Připojte každé letadlo Fano k jeho 7 tripletům, jako a Leviho graf, a také navzájem spojovat disjunktní trojčata jako lichý graf O (4).

Pro stavbu se používá velmi podobná konstrukce z PG (3,2) Higman-Simsův graf, který má Hoffman-Singletonův graf jako podgraf.

Algebraické vlastnosti

The skupina automorfismu grafu Hoffman – Singleton je skupina řádu 252 000 izomorfní s PΣU (3,5²) polopřímý produkt z projektivní speciální jednotná skupina PSU (3,5²) s cyklickou skupinou řádu 2 generovanou Frobenius automorfismus. Působí přechodně na vrcholy, na hrany a na oblouky grafu. Proto je Hoffman-Singletonův graf a symetrický graf. Stabilizátor vrcholu grafu je izomorfní s symetrická skupina S₇ na 7 písmen. Nastavený stabilizátor hrany je izomorfní s Aut (A₆) = A₆.2², kde₆ je střídavá skupina na 6 písmen. Oba dva typy stabilizátorů jsou maximálními podskupinami celé skupiny automorfismu grafu Hoffman – Singleton.

The charakteristický polynom grafu Hoffman-Singleton se rovná ${ displaystyle (x-7) (x-2) ^ {28} (x + 3) ^ {21}}$. Graf Hoffman – Singleton je tedy integrální graf: své spektrum skládá se výhradně z celých čísel.

Hoffman-Singletonův graf má přesně 100 nezávislé sady každý o velikosti 15. Každá nezávislá sada je disjunktní z přesně 7 dalších nezávislých sad. 100-vertexový graf, který spojuje disjunktní nezávislé množiny, lze rozdělit do dvou 50-vertexových podgrafů, z nichž každý je izomorfní s Hoffman-Singletonovým grafem, v neobvyklém případě samoreplikačního + multiplikačního chování.

Podgrafy a supergrafy

V grafu Hoffman-Singleton je 1260 5 cyklů a 5250 6 cyklů. Existuje 525 kopií Petersenův graf, přičemž každý 6-cyklus patří přesně každému Petersenovi. Odebrání kteréhokoli z nich zanechá kopii jedinečného (6,5) klec.^[8]

Hoffman-Singletonův graf také obsahuje mnoho kopií Möbius – Kantorův graf a Heawoodův graf, které jsou všechny bipartitní, a jejich zbarvením střídavými hodnotami +1 a -1 lze najít vlastní vektor grafu s přidruženou vlastní hodnotou −3. (Toto je jediná záporná vlastní hodnota grafu Hoffman-Singleton.) Celkově vzato tyto vlastní vektory pokrývají -3 vlastní prostor grafu Hoffman-Singleton, i když tvoří vysoce neúplný základ: existuje mnohem více Möbius – Kantorovy grafy nebo Heawoodovy grafy, než existují -3 vlastní vektory. Existuje 750 kopií grafu Heawood a graf Heawood má skupinu automorfismu řádu 336. Na druhou stranu, 750 * 336 = 252000, velikost skupiny automorfismu Hoffman-Singletonova grafu, což znamená, že Hoffman-Singletonův graf je opraven opravou libovolného grafu Heawood uvnitř. Podobně existuje 2625 kopií grafu Möbius – Kantor, který má pořadí skupin automorfismu 96, a 2625 * 96 = 252000, takže analogický výrok platí.

Heawoodův graf je zejména graf výskytu z Fano letadlo, a tak po konstrukci grafu Hoffman – Singleton 15 + 35 výše to okamžitě ukazuje mnoho míst, kde se musí vyskytovat Heawoodovy grafy. Vezměte nezávislou sadu velikosti 15 v grafu Hoffman Singleton. Je jich 100. Najděte další nezávislou množinu, která má 8 vrcholů společných s prvním. Existuje 15 takových sousedních nezávislých sad. Zlikvidujte 8 společných vrcholů. 14 vrcholů, které zůstávají, tvoří graf Heawood. Existuje tedy 100 * 15/2 = 750 grafů Heawood, jak bylo stanoveno dříve.

Hoffmanův Singletonův graf také obsahuje lichý graf O (4), Coxeterův graf a Tutte-Coxeterův graf jako podgrafy.

Vezměte libovolnou hranu grafu Hoffman-Singleton a zahoďte tyto dva vrcholy a také 12 vrcholů přímo spojených s jedním z nich. Zbývající graf je Sylvesterův graf na 36 vrcholech. Protože každou takovou hranu lze namapovat na odlišný Sylvesterův graf, v grafu Hoffmana Singletona je 175 kopií Sylvestrova grafu.

Graf Hoffmana Singletona je obsažen v Higman-Simsův graf což je tedy supergraf.

Viz také

• McKay – Miller – Širáň grafy, třída grafů včetně Hoffman-Singletonova grafu
• Tabulka největších známých grafů daného průměru a maximálního stupně

Poznámky

Reference

• Benson, C. T .; Losey, N. E. (1971), „Na grafu Hoffmana a Singletona“, Journal of Combinatorial Theory, Series B, 11 (1): 67–79, doi:10.1016/0095-8956(71)90015-3, ISSN  0095-8956, PAN  0281658
• Holton, D.A .; Sheehan, J. (1993), Petersenův graf, Cambridge University Press, s. 186 a 190, ISBN  0-521-43594-3.