Kreivi Higman Sims

Higman-Sims-graafi on 22 säännöllinen suuntaamaton graafi , jossa on 100 kärkeä ja 1100 reunaa. Graafi on ainutlaatuinen vahvasti säännöllinen graafi srg(100,22,0,6), ts. millään vierekkäisillä pisteparilla ei ole yhteisiä naapureita ja millä tahansa ei-naapuripisteparilla on kuusi yhteistä naapuria [2] . Kuvaajan rakensi ensimmäisenä Mesner [3] ja Donald J. Higman ja Charles Sims löysivät sen uudelleen vuonna 1968 tapana määritellä Higman-Sims-ryhmä . Tämä ryhmä on alaryhmä, jonka indeksi on kaksi automorfismiryhmässä. Higman-Sims-kaavio [4] .

Rakentaminen alkaa graafista M 22 , jonka 77 kärkeä ovat Steiner-järjestelmän W 22 lohkoja S(3,6,22) . Vierekkäiset kärjet määritellään ei-leikkaaviksi lohkoiksi. Tämä graafi on vahvasti säännöllinen srg(77,16,0,4), ts. millä tahansa kärjellä on 16 naapuria, kahdella vierekkäisellä kärjellä ei ole yhteisiä naapureita ja kahdella ei-viereisellä pisteellä on 4 yhteistä naapuria. Tämän graafin automorfismiryhmä on M 22 :2, missä M 22 on Mathieun ryhmä .

Higman-Sims-graafi muodostetaan lisäämällä 22 pistettä W 22 ja 100. kärki C. Huippupisteen C naapurit määritellään näiksi 22 pisteeksi. Piste on lohkon vieressä silloin ja vain, jos se kuuluu lohkoon.

Higman-Sims-graafi voidaan jakaa kahdeksi kopioksi Hoffman-Singleton-graafista 352 eri tavalla.

Algebralliset ominaisuudet

Higman-Sims-graafin automorfismiryhmä on 88 704 000:n isomorfinen ryhmä 44 ​​352 000:n Higman -Sims-ryhmän ja kertaluvun 2 syklisen ryhmän puolisuoralle tulolle [5] . Graafissa on automorfismit, jotka kuvaavat minkä tahansa reunan mihin tahansa muuhun reunaan, mikä tekee Higman-Sims-graafista reunatransitiivisen [ 6] .

Higman-Sims-graafin ominaispolynomi on . Siten Higman-Sims-graafi on kokonaislukukaavio - sen spektri koostuu kokonaan kokonaisluvuista. Graafi on myös ainoa graafi, jolla on tällainen karakteristinen polynomi, joten graafi määräytyy kokonaan sen spektrin mukaan.

Inside the Lich Grid

Higman-Sims-graafi sopii luonnollisesti Leech-hilan sisään - jos X , Y ja Z ovat kolme pistettä Leech-hilassa siten, että etäisyydet XY , XZ ja YZ ovat vastaavasti yhtä suuret, niin pisteitä T on tasan 100. Leech-hila sellainen, että kaikki etäisyydet XT , YT ja ZT ovat yhtä suuret kuin 2, ja jos yhdistämme kaksi tällaista pistettä T ja T ′ kun niiden välinen etäisyys on yhtä suuri kuin , tuloksena oleva graafi on isomorfinen Higman-Sims-graafin kanssa. Lisäksi kaikkien Leach-hilan automorfismien joukko (eli sen säilyttävän euklidisen avaruuden liike), jotka säilyttävät pisteet X , Y ja Z , on Higman-Sims-ryhmä (jos sallitaan X :n ja Y , saamme laajennuksen kaikista kertaluvun 2) graafin automorfismista. Tämä osoittaa, että Higman-Sims-ryhmä löytyy Conway-ryhmistä Co 2 (asteen 2 laajennuksella) ja Co 3 , ja siten myös Co 1 -ryhmän sisällä [7] .

Muistiinpanot

1. ↑ Hafner, 2004 , s. R77(1–32).
2. ↑ Weisstein, Eric W. Higman–Sims Graph  Wolfram MathWorld -verkkosivustolla .
3. ↑ Mesner, 1956 .
4. ↑ Higman, Sims, 1968 , s. 110-113.
5. ↑ Brouwer, Andries E. Higman–Sims-kaavio . Haettu 17. kesäkuuta 2018. Arkistoitu alkuperäisestä 14. lokakuuta 2017. (määrätön)
6. ↑ Brouwer & Haemers 1993 , s. 397-407.
7. ↑ Conway, Sloane, 1998 , s. 292 = 293.

Kirjallisuus

• Hafner PR Hoffman-Singletonin ja Higman-Simsin kaavioista // The Electronic Journal of Combinatorics . - 2004. - T. 11 , no. 1 . — S. R77(1–32) .
• Dale Marsh Mesner. Osittain tasapainotettujen epätäydellisten lohkokoesuunnitelmien ja assosiaatiokaavioiden tiettyjen kombinatoristen ominaisuuksien tutkimus, jossa on yksityiskohtainen tutkimus latinalaisen neliön ja siihen liittyvien tyyppien malleista. - Tilastolaitos, Michigan State University, 1956. - (väitöskirja).
• Donald G. Higman, Charles C. Sims. Yksinkertainen tilausryhmä 44 ​​352 000 // Mathematische Zeitschrift . - 1968. - T. 105 , no. 2 . - S. 110-113 . - doi : 10.1007/BF01110435 .
• Brouwer AE, Haemers WH Gewirtzin kuvaaja: Graafispektrien teorian harjoitus // Euro. J. Combin. - 1993. - Numero. 14 .
• John H. Conway , Neil JA Sloane . luku 10 (John H. Conway, "Three Lectures on Exceptional Groups"), §3.5 ("The Higman–Sims ja McLaughlin ryhmät") // Sphere Packings, Lattices and Groups. – 3. - Springer-Verlag , 1998. - (Grundlehren der mathematischen Wissenschaften). — ISBN 0-387-98585-9 . — ISBN 1-4419-3134-1 .