Gróf Higman Sims

A Higman-Sims gráf egy 22 szabályos irányítatlan gráf , 100 csúcsgal és 1100 éllel. A gráf egy egyedi erősen szabályos gráf srg(100,22,0,6), azaz. egyetlen szomszédos csúcspárnak sincs közös szomszédja, és bármely nem szomszédos csúcspárnak hat közös szomszédja van [2] . A gráfot először Mesner [3] szerkesztette meg, és 1968-ban Donald J. Higman és Charles Sims fedezte fel újra a Higman-Sims csoport meghatározásának módszereként, és ez a csoport egy második indexű alcsoport az automorfizmus csoportban. a Higman-Sims gráf [4] .

A konstrukció az M 22 gráfral kezdődik , amelynek 77 csúcsa a W 22 Steiner rendszer S(3,6,22) blokkja . A szomszédos csúcsok nem metsző blokkokként vannak definiálva. Ez a gráf erősen szabályos srg(77,16,0,4), azaz. bármely csúcsnak 16 szomszédja van, bármely 2 szomszédos csúcsnak nincs közös szomszédja, és bármely 2 nem szomszédos csúcsnak 4 közös szomszédja van. Ennek a grafikonnak az automorfizmuscsoportja az M 22 :2, ahol M 22 a Mathieu-csoport .

A Higman-Sims gráfot 22 pont W 22 és a 100. C csúcs összeadásával alakítjuk ki . A C csúcs szomszédai ez a 22 pont. Egy pont akkor és csak akkor szomszédos egy blokkkal, ha a blokkhoz tartozik.

A Higman-Sims gráf a Hoffman-Singleton gráf két példányára 352 módon osztható fel .

Algebrai tulajdonságok

A Higman-Sims gráf automorfizmus csoportja egy 88 704 000-es nagyságrendű izomorf csoport egy 44 352 000 rendű Higman -Sims csoport és egy 2. rendű ciklikus csoport félig közvetlen szorzatával [5] . A gráfnak vannak olyan automorfizmusai, amelyek bármely élt bármely másik élre képezik le, így a Higman-Sims gráf éltranzitív [6] .

A Higman-Sims gráf karakterisztikus polinomja: . Így a Higman-Sims gráf egy egész gráf - spektruma teljes egészében egész számokból áll. A gráf egyben az egyetlen gráf ilyen karakterisztikus polinommal, így a gráfot teljes mértékben a spektruma határozza meg.

Inside the Lich Grid

A Higman-Sims gráf természetesen illeszkedik a Leech-rács belsejébe - ha X , Y és Z három pont a Leech-rácsban úgy, hogy az XY , XZ és YZ távolságok rendre egyenlőek , akkor pontosan 100 T pontja van a Leech-rácsnak. Pióca rács úgy, hogy minden XT , YT és ZT távolság egyenlő 2-vel, és ha összekötünk két ilyen T és T ′ pontot, amikor a távolság egyenlő , akkor a kapott gráf izomorf lesz a Higman-Sims gráfhoz. Ráadásul a Leach-rács összes automorfizmusának halmaza (azaz az euklideszi tér mozgása, amely megőrzi az X , Y és Z pontokat ) egy Higman-Sims csoport (ha megengedjük az X ill . Y , megkapjuk az összes 2) rendű gráf automorfizmus kiterjesztését. Ez azt mutatja, hogy a Higman-Sims csoport a Co 2 (2. rendű kiterjesztéssel) és a Co 3 Conway csoporton belül található , és így a Co 1 csoporton belül is [7] .

Jegyzetek

1. ↑ Hafner, 2004 , p. R77(1–32).
2. ↑ Weisstein, Eric W. Higman–Sims Graph  a Wolfram MathWorld webhelyen .
3. ↑ Mesner, 1956 .
4. ↑ Higman, Sims, 1968 , p. 110–113.
5. ↑ Brouwer, Andries E. Higman–Sims grafikon . Letöltve: 2018. június 17. Az eredetiből archiválva : 2017. október 14.. (határozatlan)
6. ↑ Brouwer & Haemers 1993 , p. 397-407.
7. ↑ Conway, Sloane, 1998 , p. 292=293.

Irodalom

• Hafner PR Hoffman–Singleton és Higman–Sims grafikonjairól // the Electronic Journal of Combinatorics . - 2004. - T. 11 , sz. 1 . — S. R77(1–32) .
• Dale Marsh Mesner. Részlegesen kiegyensúlyozott, hiányos blokkkísérleti tervek és asszociációs sémák egyes kombinatorikai tulajdonságainak vizsgálata, latin négyzet és rokon típusok terveinek részletes vizsgálatával. - Statisztikai Tanszék, Michigan Állami Egyetem, 1956. - (Doktori értekezés).
• Donald G. Higman, Charles C. Sims. Egy egyszerű 44 352 000 értékű rendeléscsoport // Mathematische Zeitschrift . - 1968. - T. 105 , sz. 2 . – S. 110–113 . - doi : 10.1007/BF01110435 .
• Brouwer AE, Haemers WH A Gewirtz-gráf: Gyakorlat a gráfspektrumok elméletében // Euro. J. Combin. - 1993. - Kiadás. 14 .
• John H. Conway , Neil JA Sloane . 10. fejezet (John H. Conway, "Three Lectures on Exceptional Groups"), §3.5 ("A Higman–Sims és McLaughlin csoportok") // Sphere Packings, Lattices and Groups. — 3. - Springer-Verlag , 1998. - (Grundlehren der mathematischen Wissenschaften). — ISBN 0-387-98585-9 . — ISBN 1-4419-3134-1 .