Greve Higman Sims

Higman-Sims-grafen är en 22 reguljär oriktad graf med 100 hörn och 1100 kanter. Grafen är en unik starkt regelbunden graf srg(100,22,0,6), d.v.s. inget angränsande par av hörn har gemensamma grannar och alla icke-granne par av hörn har sex gemensamma grannar [2] . Grafen konstruerades först av Mesner [3] och återupptäcktes 1968 av Donald J. Higman och Charles Sims som ett sätt att definiera Higman-Sims-gruppen och denna grupp är en undergrupp med index två i automorfismgruppen för Higman-Sims-grafen [4] .

Konstruktionen börjar med grafen M 22 , vars 77 hörn är block S(3,6,22) i Steiner-systemet W 22 . Intilliggande hörn definieras som icke-korsande block. Denna graf är starkt regelbunden srg(77,16,0,4), dvs. vilken vertex som helst har 16 grannar, 2 närliggande hörn har inga gemensamma grannar och 2 icke-intilliggande hörn har 4 gemensamma grannar. Denna graf har M 22 : 2 som sin automorfismgrupp, där M 22 är Mathieu-gruppen .

Higman-Sims-grafen bildas genom att addera 22 punkter W 22 och den 100:e vertex C. Grannarna till vertex C definieras som dessa 22 punkter. En punkt ligger intill ett block om och bara om den tillhör blocket.

Higman-Sims-grafen kan delas upp i två kopior av Hoffman-Singleton-grafen på 352 sätt.

Algebraiska egenskaper

Higman-Sims grafautomorfismgrupp är en grupp av ordningen 88 704 000 isomorfa till den halvdirekta produkten av en Higman-Sims-grupp av ordningen 44 352 000 och en cyklisk grupp av ordningen 2 [5] . Grafen har automorfismer som mappar vilken kant som helst till vilken annan kant som helst, vilket gör Higman-Sims-grafen kanttransitiv [6] .

Det karakteristiska polynomet i Higman-Sims-grafen är . Således är Higman-Sims-grafen en heltalsgraf - dess spektrum består helt av heltal. Grafen är också den enda grafen med ett sådant karakteristiskt polynom, så att grafen helt bestäms av sitt spektrum.

Inside the Lich Grid

Higman-Sims-grafen passar naturligt inuti Leech-gittret - om X , Y och Z är tre punkter i Leech-gittret så att avstånden XY , XZ och YZ är lika , så finns det exakt 100 punkter T av Leech gitter så att alla avstånd XT , YT och ZT är lika med 2, och om vi kopplar två sådana punkter T och T ′ när avståndet mellan dem är lika med , kommer den resulterande grafen att vara isomorf till Higman-Sims-grafen. Dessutom är uppsättningen av alla automorfismer i Leach-gittret (det vill säga rörelsen av det euklidiska rummet som bevarar det) som bevarar punkterna X , Y och Z , en Higman-Sims-grupp (om vi tillåter utbyte av X och Y , vi får en förlängning av alla grafautomorfismer av ordning 2). Detta visar att Higman-Sims-gruppen finns inom Conway-grupperna Co 2 (med en förlängning av ordning 2) och Co 3 , och därmed även inom Co 1 -gruppen [7] .

Anteckningar

1. ↑ Hafner, 2004 , sid. R77(1–32).
2. ↑ Weisstein, Eric W. Higman–Sims Graph  på Wolfram MathWorld -webbplatsen .
3. ↑ Mesner, 1956 .
4. ↑ Higman, Sims, 1968 , sid. 110–113.
5. ↑ Brouwer, Andries E. Higman–Sims graf . Hämtad 17 juni 2018. Arkiverad från originalet 14 oktober 2017. (obestämd)
6. ↑ Brouwer & Haemers 1993 , sid. 397-407.
7. ↑ Conway, Sloane, 1998 , sid. 292=293.

Litteratur

• Hafner PR On the Graphs of Hoffman–Singleton och Higman–Sims // Electronic Journal of Combinatorics . - 2004. - T. 11 , nr. 1 . — S. R77(1–32) .
• Dale Marsh Mesner. En undersökning av vissa kombinatoriska egenskaper hos delvis balanserade ofullständiga experimentella blockdesigner och associationsscheman, med en detaljerad studie av design av latinska kvadrater och relaterade typer. - Institutionen för statistik, Michigan State University, 1956. - (Doktorsavhandling).
• Donald G. Higman, Charles C. Sims. En enkel grupp av order 44 352 000 // Mathematische Zeitschrift . - 1968. - T. 105 , nr. 2 . — S. 110–113 . - doi : 10.1007/BF01110435 .
• Brouwer AE, Haemers WH The Gewirtz Graph: An Exercise in the Theory of Graph Spectra // Euro. J. Combin. - 1993. - Utgåva. 14 .
• John H. Conway , Neil JA Sloane . kapitel 10 (John H. Conway, "Three Lectures on Exceptional Groups"), §3.5 ("The Higman–Sims and McLaughlin-grupper") // Sphere Packings, Lattices and Groups. — 3:a. - Springer-Verlag , 1998. - (Grundlehren der mathematischen Wissenschaften). — ISBN 0-387-98585-9 . — ISBN 1-4419-3134-1 .