Gráfico de Hoffman-Singleton
En el campo matemático de la teoría de grafos , el gráfico de Hoffman-Singleton es un gráfico no dirigido regular de 7 con 50 vértices y 175 aristas. Es el único gráfico fuertemente regular con parámetros (50,7,0,1). [5] Fue construido por Alan Hoffman y Robert Singleton mientras intentaban clasificar todos los gráficos de Moore , y es el gráfico de Moore de mayor orden que se conoce. [6] Dado que es un gráfico de Moore donde cada vértice tiene un grado 7 y la circunferencia es 5, es una jaula (7,5) .
Tome cinco pentágonos P h y cinco pentagramas Q i . Une el vértice j de P h al vértice h · i + j de Q i . (Todos los índices son módulo 5.) [7]
Tome un plano de Fano en siete elementos, como { abc, ade, afg, bef, bdg, cdf, ceg } y aplique las 2520 permutaciones pares en el abcdefg de 7 conjuntos . Canonicalice cada uno de esos planos de Fano (por ejemplo, reduciéndolos al orden lexicográfico) y descarte los duplicados. Quedan exactamente 15 aviones Fano. Cada conjunto de 3 (triplete) del conjunto abcdefg está presente en exactamente 3 planos de Fano. La incidencia entre los 35 tripletes y los 15 planos de Fano induce al PG(3,2) , con 15 puntos y 35 líneas. Para hacer el gráfico de Hoffman-Singleton, crea un vértice del gráfico para cada uno de los 15 planos de Fano y los 35 tripletes. Conecte cada plano de Fano a sus 7 tripletes, como un gráfico de Levi, y también conectar tripletas disjuntas entre sí como el gráfico impar O(4).
Se usa una construcción muy similar de PG(3,2) para construir el gráfico de Higman-Sims , que tiene el gráfico de Hoffman-Singleton como subgráfico.
El grupo de automorfismos del gráfico de Hoffman-Singleton es un grupo de orden 252,000 isomorfo a PΣU(3,5 2 ) el producto semidirecto del grupo unitario especial proyectivo PSU(3,5 2 ) con el grupo cíclico de orden 2 generado por el Automorfismo de Frobenius . Actúa transitivamente sobre los vértices, sobre las aristas y sobre los arcos del grafo. Por lo tanto, el gráfico de Hoffman-Singleton es un gráfico simétrico . El estabilizador de un vértice del gráfico es isomorfo al grupo simétrico S 7 de 7 letras. El estabilizador conjunto de un borde es isomorfo a Aut(A 6 )=A 6 .22 , donde A 6 es el grupo alterno en 6 letras. Ambos tipos de estabilizadores son subgrupos máximos de todo el grupo de automorfismos del gráfico de Hoffman-Singleton.
El polinomio característico del gráfico de Hoffman-Singleton es igual a . Por lo tanto, el gráfico de Hoffman-Singleton es un gráfico integral : su espectro consiste completamente en números enteros.
