Hrabě Higman Sims

Hrabě Higman Sims

Kresba podle konstrukce Paula R. Hafnera [1]
Pojmenoval podle Donald G Higman
Charles Sims
Vrcholy 100
žebra 1100
Poloměr 2
Průměr 2
Automorfismy 88 704 000 ( HS :2)
Vlastnosti Silně pravidelný
hraně tranzitivní
hamiltonovský
Euler
 Mediální soubory na Wikimedia Commons

Higman-Simsův graf je 22 pravidelných neorientovaných grafů se 100 vrcholy a 1100 hranami. Graf je unikátní silně regulární graf srg(100,22,0,6), tzn. žádná sousední dvojice vrcholů nemá společné sousedy a každá nesousední dvojice vrcholů má šest společných sousedů [2] . Graf byl poprvé zkonstruován Mesnerem [3] a byl znovu objeven v roce 1968 Donaldem J. Higmanem a Charlesem Simsem jako způsob, jak definovat Higman-Simsovu grupu a tato grupa je podgrupou s indexem dva ve skupině automorfismu. Higman-Simsův graf [4] .

Konstrukce začíná grafem M 22 , jehož 77 vrcholů jsou bloky S(3,6,22) Steinerovy soustavy W 22 . Sousední vrcholy jsou definovány jako neprotínající se bloky. Tento graf je silně pravidelný srg(77,16,0,4), tzn. jakýkoli vrchol má 16 sousedů, jakékoli 2 sousední vrcholy nemají žádné společné sousedy a jakékoli 2 nesousedící vrcholy mají 4 společné sousedy. Tento graf má jako grupu automorfismu M 22 : 2, kde M 22 je Mathieuova grupa .

Higman-Simsův graf je vytvořen sečtením 22 bodů W 22 a 100. vrcholu C. Sousedé vrcholu C jsou definováni jako těchto 22 bodů. Bod sousedí s blokem právě tehdy, pokud do bloku patří.


Higman-Simsův graf lze rozdělit na dvě kopie Hoffman-Singletonova grafu 352 způsoby.

Algebraické vlastnosti

Skupina automorfismu Higman-Simsova grafu je grupa řádu 88 704 000 izomorfní k polopřímému součinu Higman-Simsovy grupy řádu 44 352 000 a cyklické grupy řádu 2 [5] . Graf má automorfismy, které mapují jakoukoli hranu na jakoukoli jinou hranu, díky čemuž je Higman-Simsův graf hraně tranzitivní [6] .

Charakteristickým polynomem Higman-Simsova grafu je . Higman-Simsův graf je tedy celočíselný graf – jeho spektrum se skládá výhradně z celých čísel. Graf je také jediným grafem s tak charakteristickým polynomem, takže graf je zcela určen svým spektrem.

Uvnitř Lich Grid

Higman-Simsův graf přirozeně zapadá dovnitř mřížky Leech - pokud X , Y a Z jsou tři body v mřížce Leech tak, že vzdálenosti XY , XZ a YZ jsou stejné , pak existuje přesně 100 bodů T Leech mřížka taková, že všechny vzdálenosti XT , YT a ZT jsou rovné 2, a pokud spojíme dva takové body T a T ′, když je vzdálenost mezi nimi rovna , bude výsledný graf izomorfní s Higman-Simsovým grafem. Navíc množina všech automorfismů Leachovy mřížky (tedy pohybu euklidovského prostoru, které ji zachovávají), které zachovávají body X , Y a Z , je Higman-Simsova grupa (pokud připustíme výměnu X a Y , dostaneme rozšíření všech grafových automorfismů řádu 2). To ukazuje, že skupina Higman-Sims se nachází uvnitř Conwayových skupin Co 2 (s rozšířením řádu 2) a Co 3 , a tedy také uvnitř skupiny Co 1 [7] .

Poznámky

  1. ↑ Hafner, 2004 , str. R77(1–32).
  2. ↑ Weisstein, Eric W. Higman–Sims Graph  na webu Wolfram MathWorld .
  3. ↑ Mesner, 1956 .
  4. ↑ Higman, Sims, 1968 , str. 110–113.
  5. ↑ Brouwer, Andries E. Higman–Simsův graf . Získáno 17. června 2018. Archivováno z originálu 14. října 2017.
  6. ↑ Brouwer & Haemers 1993 , str. 397-407.
  7. ↑ Conway, Sloane, 1998 , str. 292=293.

Literatura