Conde Higman Sims

El gráfico de Higman-Sims es un gráfico no dirigido regular de 22 con 100 vértices y 1100 aristas. El gráfico es un único gráfico fuertemente regular srg(100,22,0,6), es decir ningún par de vértices adyacentes tiene vecinos comunes y cualquier par de vértices no vecinos tiene seis vecinos comunes [2] . El gráfico fue construido por primera vez por Mesner [3] y fue redescubierto en 1968 por Donald J. Higman y Charles Sims como una forma de definir el grupo Higman-Sims y este grupo es un subgrupo con índice dos en el grupo de automorfismos de el gráfico de Higman-Sims [4] .

La construcción comienza con el grafo M 22 , cuyos 77 vértices son bloques S(3,6,22) del sistema de Steiner W 22 . Los vértices adyacentes se definen como bloques que no se intersecan. Este gráfico es fuertemente regular srg(77,16,0,4), es decir cualquier vértice tiene 16 vecinos, 2 vértices adyacentes no tienen vecinos comunes y 2 vértices no adyacentes tienen 4 vecinos comunes. Este gráfico tiene M 22 :2 como su grupo de automorfismos, donde M 22 es el grupo de Mathieu .

El gráfico de Higman-Sims se forma sumando 22 puntos W 22 y el vértice número 100 C. Los vecinos del vértice C se definen como estos 22 puntos. Un punto es adyacente a un bloque si y solo si pertenece al bloque.

El gráfico de Higman-Sims se puede dividir en dos copias del gráfico de Hoffman-Singleton de 352 maneras.

Propiedades algebraicas

El grupo de automorfismo gráfico de Higman-Sims es un grupo de orden 88.704.000 isomorfo al producto semidirecto de un grupo de Higman-Sims de orden 44.352.000 y un grupo cíclico de orden 2 [5] . El gráfico tiene automorfismos que asignan cualquier borde a cualquier otro borde, lo que hace que el gráfico de Higman-Sims sea transitivo en el borde [6] .

El polinomio característico del gráfico de Higman-Sims es . Por lo tanto, el gráfico de Higman-Sims es un gráfico de enteros : su espectro consiste completamente en números enteros. El gráfico es también el único gráfico con un polinomio tan característico, por lo que el gráfico está completamente determinado por su espectro.

Dentro de la Red Lich

El gráfico de Higman-Sims encaja 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 iguales respectivamente, entonces hay exactamente 100 puntos T de la red. Leech la red tal 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 igual a , el gráfico resultante será isomorfo al gráfico de Higman-Sims. Además, el conjunto de todos los automorfismos de la red de Leach (es decir, el movimiento del espacio euclidiano que la conserva) que conservan los puntos X , Y y Z , es un grupo de Higman-Sims (si permitimos el intercambio de X y Y , obtenemos una extensión de todos los automorfismos de grafos de orden 2). Esto muestra que el grupo de Higman-Sims se encuentra dentro de los grupos de Conway Co 2 (con una extensión de orden 2) y Co 3 , y por lo tanto también dentro del grupo Co 1 [7] .

Notas

1. ↑ Hafner, 2004 , pág. R77(1–32).
2. ↑ Weisstein, Eric W. Higman–Sims Graph  en el sitio web de Wolfram MathWorld .
3. ↑ Mesner, 1956 .
4. ↑ Higman, Sims, 1968 , pág. 110–113.
5. ↑ Brouwer, Andries E. Higman–Sims graph . Consultado el 17 de junio de 2018. Archivado desde el original el 14 de octubre de 2017. (indefinido)
6. ↑ Brouwer y Haemers 1993 , pág. 397-407.
7. ↑ Conway, Sloane, 1998 , pág. 292=293.

Literatura

• Hafner PR Sobre los gráficos de Hoffman-Singleton y Higman-Sims // Electronic Journal of Combinatorics . - 2004. - T. 11 , núm. 1 . — S. R77(1–32) .
• Dale Marsh Mesner. 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. - Departamento de Estadística, Universidad Estatal de Michigan, 1956. - (Tesis de Doctorado).
• Donald G. Higman, Charles C. Sims. Un grupo simple de orden 44,352,000 // Mathematische Zeitschrift . - 1968. - T. 105 , núm. 2 . — S. 110–113 . -doi : 10.1007/ BF01110435 .
• Brouwer AE, Haemers WH El gráfico de Gewirtz: un ejercicio de teoría de los espectros de gráficos // Euro. J. Combina. - 1993. - Edición. 14 _
• John H. Conway , Neil JA Sloane . capítulo 10 (John H. Conway, "Tres conferencias sobre grupos excepcionales"), §3.5 ("Los grupos Higman-Sims y McLaughlin") // Empaquetaduras de esferas, celosías y grupos. — 3er. - Springer-Verlag , 1998. - (Grundlehren der mathematischen Wissenschaften). — ISBN 0-387-98585-9 . — ISBN 1-4419-3134-1 .