Gráfico de Higman-Sims

En la teoría matemática de grafos , el grafo de Higman-Sims es un grafo no dirigido 22- regular con 100 vértices y 1100 aristas. Es el único grafo fuertemente regular srg(100,22,0,6), donde ningún par de vértices vecinos comparte un vecino común y cada par de vértices no vecinos comparte seis vecinos comunes. ^[²^] Fue construido por primera vez por Mesner (1956) ^[³^] y redescubierto en 1968 por Donald G. Higman y Charles C. Sims como una forma de definir el grupo de Higman-Sims , un subgrupo de índice dos en el grupo de automorfismos del grafo de Hoffman-Singleton. ^[⁴^]

Construcción

Según el gráfico M22

Toma el grafo M22 , un grafo fuertemente regular srg(77,16,0,4) y auméntalo con 22 nuevos vértices que corresponden a los puntos de S(3,6,22), cada bloque conectado a sus puntos, y un vértice adicional C conectado a los 22 puntos.

A partir del gráfico de Hoffman-Singleton

En el grafo de Hoffman-Singleton existen 100 conjuntos independientes de tamaño 15. Crea un nuevo grafo con 100 vértices correspondientes y conecta aquellos cuyos conjuntos independientes tengan exactamente 0 u 8 elementos en común. El grafo de Higman-Sims resultante se puede particionar en dos copias del grafo de Hoffman-Singleton de 352 maneras.

Desde un cubo

Toma un cubo con vértices etiquetados como 000, 001, 010, ..., 111. Toma los 70 posibles conjuntos de 4 vértices y conserva solo aquellos cuyo XOR se evalúa como 000; hay 14 de estos conjuntos de 4, que corresponden a las 6 caras + 6 rectángulos diagonales + 2 tetraedros de paridad. Este es un diseño de bloques 3-(8,4,1) en 8 puntos, con 14 bloques de tamaño de bloque 4, cada punto aparece en 7 bloques, cada par de puntos aparece 3 veces, cada triplete de puntos aparece exactamente una vez. Permuta los 8 vértices originales de cualquiera de 8! = 40320 maneras y descarta los duplicados. Hay entonces 30 maneras diferentes de volver a etiquetar los vértices (es decir, 30 diseños diferentes que son todos isomorfos entre sí por permutación de los puntos). Esto se debe a que hay 1344 automorfismos y 40320/1344 = 30.

Crea un vértice para cada uno de los 30 diseños y para cada fila de cada diseño (hay 70 filas en total, cada fila es un conjunto de 4 elementos de 8 y aparece en 6 diseños). Conecta cada diseño con sus 14 filas. Conecta los diseños disjuntos entre sí (cada diseño es disjunto con otros 8). Conecta las filas entre sí si tienen exactamente un elemento en común (hay 4x4 = 16 vecinos de este tipo). El grafo resultante es el grafo de Higman-Sims. Las filas están conectadas a otras 16 filas y a 6 diseños == grado 22. Los diseños están conectados a 14 filas y 8 diseños disjuntos == grado 22. Por lo tanto, los 100 vértices tienen grado 22 cada uno.

Propiedades algebraicas

El grupo de automorfismos del grafo de Higman-Sims es un grupo de orden 88.704.000 isomorfo al producto semidirecto del grupo de Higman-Sims de orden 44.352.000 con el grupo cíclico de orden 2. ^{[ 5 ]} Posee automorfismos que transforman cualquier arista en cualquier otra, lo que convierte al grafo de Higman-Sims en un grafo transitivo por aristas . ^{[ 6 ]} Los elementos externos inducen permutaciones impares en el grafo. Como se mencionó anteriormente , existen 352 maneras de particionar el grafo de Higman-Sims en un par de grafos de Hoffman-Singleton; estas particiones se presentan en realidad en 2 órbitas de tamaño 176 cada una, y los elementos externos del grupo de Higman-Sims intercambian estas órbitas. ^{[ 7 ]}

El polinomio característico del grafo de Higman-Sims es ( x − 22)( x − 2) ⁷⁷ ( x + 8) ²² . Por lo tanto, el grafo de Higman-Sims es un grafo integral : su espectro está compuesto enteramente por números enteros. Además, es el único grafo con este polinomio característico, lo que lo convierte en un grafo determinado por su espectro.

Dentro de la red de sanguijuelas

Una proyección del grafo de Higman-Sims dentro de la red de Leech.

El gráfico de Higman-Sims aparece naturalmente dentro de la red de Leech : si X , Y y Z son tres puntos en la red de Leech tales que las distancias XY , XZ e YZ son $2,{\sqrt {6}},{\sqrt {6}}$ respectivamente, entonces hay exactamente 100 puntos de la red de Leech T tales que todas las distancias XT , YT y ZT son iguales a 2, y si conectamos dos de esos puntos T y T ′ cuando la distancia entre ellos es ${\sqrt {6}}$ El grafo resultante es isomorfo al grafo de Higman-Sims. Además, el conjunto de todos los automorfismos del retículo de Leech (es decir, las congruencias euclidianas que lo fijan) que fijan cada uno de X , Y y Z es el grupo de Higman-Sims (si permitimos intercambiar X e Y , se obtiene la extensión de orden 2 de todos los automorfismos de grafos). Esto demuestra que el grupo ^de Higman-Sims aparece dentro de los grupos de Conway Co ₂ (con su extensión de orden 2) y Co ₃ , y por consiguiente también Co _1.^[⁸ ]

Referencias

↑ Hafner, PR (2004). "Sobre los grafos de Hoffman - Singleton y Higman - Sims" (PDF) . The Electronic Journal of Combinatorics . 11 (1) R77: R77(1–32). doi : 10.37236/1830 ..
↑ Weisstein, Eric W. "Grafo de Higman - Sims" . MathWorld .
↑ Mesner, Dale Marsh (1956). Una investigación de ciertas propiedades combinatorias de diseños experimentales de bloques incompletos parcialmente balanceados y esquemas de asociación, con un estudio detallado de diseños de cuadrados latinos y tipos relacionados (Tesis doctoral). Departamento de Estadística, Universidad Estatal de Michigan. MR 2612633 .
^ Higman, Donald G.; Sims, Charles C. (1968). «Un grupo simple de orden 44.352.000» (PDF) . Mathematische Zeitschrift . 105 (2): 110– 113. doi : 10.1007/BF01110435 . hdl : 2027.42/46258 . S2CID 32803979 . .
↑ Brouwer, Andries E. "Gráfico de Higman - Sims" .
↑ Brouwer, AE y Haemers, WH "El grafo de Gewirtz: un ejercicio en la teoría de los espectros de grafos." Euro. J. Combin. 14, 397 – 407, 1993.
↑ Conway, JH ; Curtis, RT; Norton, SP ; Parker, RA ; Wilson, RA (1985). Atlas de grupos finitos: subgrupos maximales y caracteres ordinarios para grupos simples . Con la asistencia computacional de JG Thackray. Oxford University Press. ISBN 978-019853199-9.
^ Conway, John H .; Sloane, Neil JA (diciembre de 2010). Empaquetaduras, Retículos y Grupos de Esferas . Grundlehren der mathematischen Wissenschaften (3ª ed.). Springer-Verlag . ISBN 978-1-4419-3134-4.capítulo 10 (John H. Conway, "Tres conferencias sobre grupos excepcionales"), §3.5 ("Los grupos Higman-Sims y McLaughlin"), págs. 292-293 .

[1] Hafner, PR (2004). "Sobre los grafos de Hoffman - Singleton y Higman - Sims" (PDF) . The Electronic Journal of Combinatorics . 11 (1) R77: R77(1–32). doi : 10.37236/1830 ..

[2] Weisstein, Eric W. "Grafo de Higman - Sims" . MathWorld .

[3] Mesner, Dale Marsh (1956). Una investigación de ciertas propiedades combinatorias de diseños experimentales de bloques incompletos parcialmente balanceados y esquemas de asociación, con un estudio detallado de diseños de cuadrados latinos y tipos relacionados (Tesis doctoral). Departamento de Estadística, Universidad Estatal de Michigan. MR 2612633 .

[4] Higman, Donald G.; Sims, Charles C. (1968). «Un grupo simple de orden 44.352.000» (PDF) . Mathematische Zeitschrift . 105 (2): 110– 113. doi : 10.1007/BF01110435 . hdl : 2027.42/46258 . S2CID 32803979 . .

[5] Brouwer, Andries E. "Gráfico de Higman - Sims" .

[6] Brouwer, AE y Haemers, WH "El grafo de Gewirtz: un ejercicio en la teoría de los espectros de grafos." Euro. J. Combin. 14, 397 – 407, 1993.

[7] Conway, JH ; Curtis, RT; Norton, SP ; Parker, RA ; Wilson, RA (1985). Atlas de grupos finitos: subgrupos maximales y caracteres ordinarios para grupos simples . Con la asistencia computacional de JG Thackray. Oxford University Press. ISBN 978-019853199-9.

[8] Conway, John H .; Sloane, Neil JA (diciembre de 2010). Empaquetaduras, Retículos y Grupos de Esferas . Grundlehren der mathematischen Wissenschaften (3ª ed.). Springer-Verlag . ISBN 978-1-4419-3134-4.capítulo 10 (John H. Conway, "Tres conferencias sobre grupos excepcionales"), §3.5 ("Los grupos Higman-Sims y McLaughlin"), págs. 292-293 .

[

[

[

[ 5 ]

[ 6 ]

[ 7 ]

de