Hoffman-Singleton grófja

Hoffman grófja – Singleton

Valaki után elnevezve	Alan Hoffman Robert R. Singleton
Csúcsok	ötven
borda	175
Sugár	2
Átmérő	2 [1]
Heveder	5 [1]
Automorfizmusok	252 000 ( tápegység(3,5 2 ):2) [2]
Kromatikus szám	négy
Kromatikus index	7 [3]
Nemzetség	29 [4]
Tulajdonságok	Erősen szabályos szimmetrikus Hamiltoni egész ketrec Moore-grafikon
Médiafájlok a Wikimedia Commons oldalon

A Hoffman-Singleton gráf egy 7 homogén irányítatlan gráf , 50 csúcsgal és 175 éllel. A gráf az egyetlen erősen szabályos gráf paraméterekkel [5] . A gráfot Alan Hoffman és Robert Singleton állította össze, amikor az összes Moore-gráfot osztályozni próbálták , és ez a legmagasabb rendű Moore-gráf, amelyről ismert, hogy ilyen gráf létezik [6] . Mivel a gráf egy Moore-gráf , amelyben minden csúcsnak 7 foka van, és a gráf kerülete 5, a gráf egy cella . $(50,7,0,1)$ $(7,5)$

Épület

A Hoffman-Singleton-gráfok elkészítésének számos módja van.

Építés ötszögek és pentagramok alapján

Vegyünk 5 ötszöget és 5 pentagramot úgy, hogy az ötszög csúcsa szomszédos legyen a csúcsaival , és az ötszög és a pentagram csúcsa szomszédos a és a pentagram csúcsaival . Kössük össze a grafikon tetejét a grafikon tetejével . (Minden index 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}$

Építés hármasokból és Fano repülőgépekből

Vegyünk egy Fano repülőgépet , és fontoljuk meg a 7 pont megváltoztatását, hogy 30 Fano repülőgépet kapjunk. Válasszunk egyet ezek közül a síkok közül. 14 másik Fano repülőgép van, amelyeknek pontosan egy közös hármasa ("vonal") van a kiválasztott síkkal. Vegyük ezt a 15 Fano síkot, és dobjuk el a maradék 15-öt. Tekintsünk 7 C 3 = 35 hármast 7 számból. Most összekötünk (egy éllel) egy hármast az ezt a hármast tartalmazó Fano síkokkal, és összekötünk egymással nem metsző hármasokat is. Az így kapott gráf egy Hoffman-Singleton gráf, amely 50 csúcsból áll, amelyek 35 tripletnek és 15 Fano-síknak felelnek meg, és minden csúcsnak 7 foka van. A Fano-síknak megfelelő csúcsok definíció szerint 7 tripletthez kapcsolódnak, mivel a Fano-sík 7 sora van. Minden hármas 3 különböző Fano síkhoz kapcsolódik, amelyek tartalmazzák, és 4 másik hármashoz, amelyekkel nem metszik egymást.

Algebrai tulajdonságok

A Hoffman-Singleton gráf automorfizmuscsoportja egy 252000 rendű csoport, és izomorf a PΣU(3,5 2 ), a projektív speciális unitárius csoport félig közvetlen szorzatával. $tápegység(3.5^{2})$ és a Frobenius-endomorfizmus által generált 2. rendű ciklikus csoport . Az automorfizmus tranzitív módon hat a gráf csúcsaira és éleire. Így a Hoffman-Singleton gráf szimmetrikus gráf . A gráf csúcsstabilizátora 7 betűn izomorf a szimmetrikus csoporttal . Az élkészlet-stabilizátor izomorf -val , ahol egy 6 betűből álló váltakozó csoport . Mindkét típusú stabilizátor a Hoffman-Singleton gráf teljes automorfizmus csoportjának maximális alcsoportja. $S_7$ $Aut(A_{6})=A_{6}\cdot 2^{2}$ $A_{6}$

A Hoffman-Singleton gráf karakterisztikus polinomja : . Így a Hoffman-Singleton gráf egész szám - spektruma teljes egészében egész számokból áll. ${\megjelenítési stílus (x-7)(x-2)^{28}(x+3)^{21))$

Részgráfok

Csak azt a tényt felhasználva, hogy a Hoffman-Singleton gráf szigorúan szabályos paraméterekkel , megmutathatjuk, hogy 1260 5 hosszúságú ciklus van benne. $(50,7,0,1)$

Ezenkívül a Hoffman-Singleton-gróf a Petersen-gróf 525 példányát tartalmazza . Az egyik eltávolítása az egyetlen cella másolatát kapja [ 7] . $(6,5)$

Lásd még

Adott átmérőjű és maximális fokszámú ismert legnagyobb grafikonok táblázata

Jegyzetek

↑ 1 2 Weisstein, Eric W. Hoffman-Singleton grafikon a Wolfram MathWorld webhelyen .
↑ Hafner, 2003 , p. 7-12.
↑ Royle .
↑ Conder, Stokes, 2014 .
↑ Browser .
↑ Hoffman, Singleton, 1960 , p. 497–504.
↑ Wong, 1979 , p. 407–409.

Irodalom

PR Hafner. A Hoffman-Singleton gráf és automorfizmusai // J. Algebraic Combin. - 2003. - T. 18 .
G. Royle. Re: Mi a Hoffman-Singleton élkromatikus száma? . [email protected] közzététel. (2004. szeptember 28.). (határozatlan) (nem elérhető link)
MDE Conder, K. Stokes. A Hoffman-Singleton gráf minimális nemzetségbeágyazása // preprint. — 2014.
C. T. Benson, N. E. Losey. Hoffman és Singleton grafikonján // Journal of Combinatorial Theory. B. sorozat – 11. évf . 1 . – S. 67–79 . — ISSN 0095-8956 . - doi : 10.1016/0095-8956(71)90015-3 .
D. A. Holton, J. Sheehan. A Petersengraph . - Cambridge University Press , 1993. - S. 186 , 190. - ISBN 0-521-43594-3 . .
Andries E. Brouwer. Hoffman-Singleton gráf . Letöltve: 2016. szeptember 7. Az eredetiből archiválva : 2016. március 3. (határozatlan)
Alan J. Hoffman, Robert R. Singleton. Moore-gráfok 2-es és 3-as átmérővel // IBM Journal of Research and Development. - 1960. - V. 5 , sz. 4 . – S. 497–504 . - doi : 10.1147/rd.45.0497 .
Pak-Ken Wong. Az 5-ös kerület és a 6-os vegyérték legkisebb gráfjának egyediségéről // Journal of Graph Theory. - 1979. - T. 3 . – S. 407–409 . - doi : 10.1002/jgt.3190030413 .