Grafo de Higman-Sims

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Grafo de Higman–Sims
Higman Sims Graph.svg
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[editar | editar código-fonte]

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[editar | editar código-fonte]

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. Eric W. Weisstein, Grafo de Higman–Sims em MathWorld
  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