Grafo de Higman-Sims

Grafo de Higman–Sims

Desenho baseado em uma construção de Paul R. Hafner[1]
Nomeado em honra a Donald G. Higman
Charles C. Sims
vértices 100
arestas 1100
Raio 2
Diâmetro 2
Cintura 4
Automorfismos 88704000 (HS:2)
Propriedades Fortemente regular
Aresta-transitivo
Hamiltoniano
Euleriano
Integral
As partes em separado da construção de Hafner.

No campo da matemática da teoria dos grafos, o Grafo de Higman–Sims é um grafo não direcionado, 22-regular com 100 vértices e 1100 arestas. É o único grafo fortemente regular com 100 vértices e valência 22, onde nenhum par de vértices vizinhos partilham um vizinho comum e cada par de vértices não-vizinhos partilham seis vizinhos comuns.[2] Foi construído em 1968 por Donald G. Higman e Charles C. Sims como uma forma de definir o grupo de Higman–Sims, e este grupo é um subgrupo do índice dois no grupo de automorfismos do grafo de Higman–Sims.[3]

A construção começa com o grafo M22, cujos 77 vértices são os blocos do S(3,6,22) sistema de Steiner W22. Vértices adjacentes são definidos como blocos disjuntos. Este grafo é fortemente regular; qualquer vértice tem 16 vizinhos, quaisquer dois vértices adjacentes não tem vizinhos comuns, e quaisquer dois vértices não adjacentes têm 4 vizinhos comuns. Este grafo tem M22:2 como seu automorfismo de grupo, sendo M22 o seu grupo Mathieu.

O grafo de Higman–Sims é formado anexando os 22 pontos de W22 e um 100º vértice C. Os vizinhos de C são definidos ser estes 22 pontos. Um ponto adjacente a um bloco é definido ser aquele que está incluído.

Um grafo de Higman–Sims pode ser particionado em duas cópias do grafo de Hoffman–Singleton de 352 maneiras.

Propriedades algébricas

O grupo de automorfismo do grafo de Higman–Sims graph é um grupo de ordem 88704000 isomórfico ao produto semidireto do grupo de Higman–Sims de ordem 44352000 com o grupo cíclico de ordem 2.[4] Ele tem automorfismos que levam qualquer aresta para outra aresta, fazendo o grafo de Higman–Sims um grafo aresta-transitivo.[5]

O polinômio característico do grafo de Higman–Sims graph is (x − 22)(x − 2)77(x + 8)22. Portanto o grafo de Higman–Sims é um grafo integral: seu espectro de grafo consiste inteiramente de inteiros. Ele é também considerado o único grafo com este polinômio característico, fazendo dele um grafo determinado por seu espectro.

Dentro da malha de Leech

Uma projeção do grafo de Higman-Sims dentro da malha de Leech.

O grafo de Higman-Sims ocorre naturalmente no interior da malha de Leech: se X, Y e Z são três pontos na malha de Leech tais que as distâncias XY, XZ e YZ são 2, 3, 3 respectivamente, então há exatamente 100 pontos da malha de Leech T de tal forma que todas as distâncias XT, YT e ZT são iguais a 2, e se ligarmos dois pontos, tais T e T′ quando a distância entre eles é 2, O grafo resultante é isomorfo ao grafo de Higman-Sims. Além disso, o conjunto de todos os automorfismos da malha de Leech (Isto é, congruências euclidiana fixando-a) que fixam cada um dos X, Y e Z é o grupo de Higman–Sims (Se nós permitirmos trocar X e Y, a extensão de ordem 2 de todos os automorfismos de grafos é obtida). Isso mostra que o grupo Higman-Sims ocorre dentro do grupo de Conway Co2 (com sua extensão de ordem 2) e Co3, e, conseqüentemente, também Co1.[6]

Referências

  1. ↑ HAFNER, P. R. (2004). «On the Graphs of Hoffman–Singleton and Higman–Sims» (PDF). The Electronic Journal of Combinatorics. 11 (1). pp. R77(1–32) 
  2. ↑ Weisstein, Eric W. «Grafo de Higman–Sims». MathWorld (em inglês) 
  3. ↑ HIGMAN, Donald G.; SIMS, Charles C. (1968). «A simple group of order 44,352,000». Mathematische Zeitschrift. 105 (2). pp. 110–113. doi:10.1007/BF01110435 
  4. ↑ BROUWER, Andries E. «Higman–Sims graph» 
  5. ↑ Brouwer, A. E. and Haemers, W. H. "The Gewirtz Graph: An Exercise in the Theory of Graph Spectra." Euro. J. Combin. 14, 397–407, 1993.
  6. ↑ Conway, John H.; Sloane, Neil J. A. «10 (John H. Conway, "Three Lectures on Exceptional Groups"), §3.5 ("The Higman–Sims and McLaughlin groups")». Sphere Packings, Lattices and Groups. Col: Grundlehren der mathematischen Wissenschaften 3 ed. [S.l.]: Springer-Verlag. p. 292–293. ISBN 1441931341