En teoría matemática de grafos , el grafo de Higman-Sims es un grafo no dirigido regular de 22 con 100 vértices y 1100 aristas. Es el único gráfico 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. [2] 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 Higman-Sims , un subgrupo del índice dos en el grupo de automorfismos de Higman. –Gráfica de Sims. [3]
Gráfico Higman-Sims | |
---|---|
Lleva el nombre de | Donald G. Higman Charles C. Sims |
Vértices | 100 |
Bordes | 1100 |
Radio | 2 |
Diámetro | 2 |
Circunferencia | 4 |
Automorfismos | 88,704,000 ( SA : 2) |
Propiedades | Euleriano hamiltoniano transitivo de bordes fuertemente regular |
Tabla de gráficos y parámetros |
Construcción
Desde el gráfico M22
Tome el gráfico M22 , un gráfico srg (77,16,0,4) fuertemente regular y auméntelo con 22 nuevos vértices correspondientes a los puntos de S (3,6,22), cada bloque está conectado a sus puntos, y uno vértice adicional C conectado a los 22 puntos.
Del gráfico de Hoffman-Singleton
Hay 100 conjuntos independientes de tamaño 15 en el gráfico Hoffman-Singleton . Cree un nuevo gráfico con 100 vértices correspondientes y conecte los vértices cuyos conjuntos independientes correspondientes tengan exactamente 0 u 8 elementos en común. El gráfico de Higman-Sims resultante se puede dividir en dos copias del gráfico de Hoffman-Singleton de 352 formas.
De un cubo
Tome un cubo con vértices etiquetados como 000, 001, 010, ..., 111. Tome los 70 posibles conjuntos de 4 vértices y retenga solo aquellos cuyo XOR se evalúe como 000; hay 14 de estos 4 conjuntos, correspondientes a las 6 caras + 6 rectángulos diagonales + 2 tetraedros de paridad. Este es un diseño de bloque de 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 ocurre exactamente una vez. ¡Permuta los 8 vértices originales en cualquiera de los 8! = 40320 vías y descartar duplicados. Entonces hay 30 formas 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.
Cree un vértice para cada uno de los 30 diseños y para cada fila de cada diseño (hay 70 filas de este tipo en total, cada fila es un conjunto de 4 de 8 y aparece en 6 diseños). Conecte cada diseño a sus 14 filas. Conecte diseños disjuntos entre sí (cada diseño está disjunto con otros 8). Conecte filas entre sí si tienen exactamente un elemento en común (hay 4x4 = 16 vecinos de este tipo). El gráfico resultante es el gráfico de Higman-Sims. Las filas están conectadas a otras 16 filas ya 6 diseños == grado 22. Los diseños están conectados a 14 filas y 8 diseños separados == grado 22. Por lo tanto, los 100 vértices tienen un grado 22 cada uno.
Propiedades algebraicas
El grupo de automorfismos del gráfico de Higman-Sims es un grupo de orden 88,704,000 isomórfico al producto semidirecto del grupo de Higman-Sims de orden 44,352,000 con el grupo cíclico de orden 2. [4] Tiene automorfismos que llevan cualquier ventaja a cualquier otro. edge, lo que hace que el gráfico de Higman-Sims sea un gráfico de borde transitivo . [5]
El polinomio característico de la gráfica de Higman-Sims es ( x - 22) ( x - 2) 77 ( x + 8) 22 . Por lo tanto, el gráfico de Higman-Sims es un gráfico integral : su espectro consta completamente de números enteros. También es el único gráfico con este polinomio característico, lo que lo convierte en un gráfico determinado por su espectro.
Dentro de la celosía Leech
El gráfico de Higman-Sims ocurre naturalmente dentro de la celosía Leech : si X , Y y Z son tres puntos en la celosía Leech de manera que las distancias XY , XZ e YZ sonrespectivamente, entonces hay exactamente 100 puntos de celosía de Leech T tales que todas las distancias XT , YT y ZT son iguales a 2, y si conectamos dos de tales puntos T y T ′ cuando la distancia entre ellos es, el gráfico resultante es isomorfo al gráfico de Higman-Sims. Además, el conjunto de todos los automorfismos del retículo Leech (es decir, las congruencias euclidianas que lo fijan) que fijan cada uno de X , Y y Z es el grupo Higman-Sims (si permitimos intercambiar X e Y , la extensión de orden 2 de todos se obtienen automorfismos gráficos). Esto muestra que el grupo Higman-Sims ocurre dentro de los grupos de Conway Co 2 (con su extensión de orden 2) y Co 3 , y consecuentemente también Co 1 . [6]
Referencias
- ^ Hafner, PR (2004). "Sobre los gráficos de Hoffman-Singleton y Higman-Sims" (PDF) . la Revista Electrónica de Combinatoria . 11 (1): R77 (1–32). doi : 10.37236 / 1830 . Enlace externo en
|journal=
( ayuda ) . - ^ Weisstein, Eric W. "Gráfico de Higman-Sims" . MathWorld .
- ^ 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 ..
- ^ Brouwer, Andries E. "Gráfico de Higman-Sims" .
- ^ Brouwer, AE y Haemers, WH "El gráfico de Gewirtz: un ejercicio en la teoría de espectros gráficos". Euro. J. Combin. 14, 397–407, 1993.
- ^ Conway, John H .; Empaquetaduras, celosías y grupos de esferas Sloane, Neil JA . Grundlehren der mathischen Wissenschaften (3ª ed.). Springer-Verlag . ISBN 1-4419-3134-1. capítulo 10 (John H. Conway, "Tres conferencias sobre grupos excepcionales"), §3.5 ("Los grupos Higman-Sims y McLaughlin"), págs. 292-293.
- 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