En el campo matemático de la teoría de grafos , el gráfico de Hoffman-Singleton es un gráfico no dirigido de 7 regulares 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 orden más alto que se sabe que existe. [6] Dado que es un gráfico de Moore donde cada vértice tiene grado 7 y la circunferencia es 5, es una jaula (7,5) .
A continuación se muestran algunas construcciones del gráfico de Hoffman-Singleton. [7]
Tome cinco pentágonos Ph y cinco pentagramos Qi . Une el vértice j de P h con el 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 plano de Fano (por ejemplo, reduciéndolo al orden lexicográfico) y descarte los duplicados. Quedan exactamente 15 aviones Fano. Cada 3 conjuntos (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 PG(3,2) , con 15 puntos y 35 líneas. Para hacer el gráfico de Hoffman-Singleton, cree 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 conecte tripletes disjuntos entre sí como el gráfico impar O(4).
Se utiliza una construcción muy similar a partir de PG(3,2) para construir el gráfico de Higman-Sims , que tiene el gráfico de Hoffman-Singleton como subgrafo.
Sea el conjunto . Defina una operación binaria tal que para cada y en , . Entonces, el gráfico de Hoffman-Singleton tiene vértices y existe un borde entre y siempre para algunos . [8] (Aunque los autores usan la palabra "grupoide", es en el sentido de una función binaria o magma, no en el sentido de la teoría de categorías. También tenga en cuenta que hay un error tipográfico en la fórmula del artículo: el artículo tiene en el último término, pero eso no produce el gráfico de Hoffman-Singleton. En cambio, debería ser como está escrito aquí [9] ) .
El grupo de automorfismo 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 Automorfismo de Frobenius . Actúa transitivamente sobre los vértices, sobre las aristas y sobre los arcos del grafo. Por tanto, la gráfica de Hoffman-Singleton es una gráfica simétrica . Como grupo de permutaciones de 50 símbolos, se puede generar mediante las dos permutaciones siguientes aplicadas de forma recursiva [10]
y
El estabilizador de un vértice del gráfico es isomorfo al grupo simétrico S 7 de 7 letras. El estabilizador establecido de un borde es isomorfo a Aut(A 6 )=A 6 .2 2 , donde A 6 es el grupo alterno de 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 tanto, el gráfico de Hoffman-Singleton es un gráfico integral : su espectro se compone enteramente de números enteros.
La gráfica de Hoffman-Singleton tiene exactamente 100 conjuntos independientes de tamaño 15 cada uno. Cada conjunto independiente está separado de exactamente otros 7 conjuntos independientes. El gráfico de 100 vértices que conecta conjuntos independientes disjuntos se puede dividir en dos subgrafos de 50 vértices, cada uno de los cuales es isomorfo al gráfico de Hoffman-Singleton, en un caso inusual de comportamiento de autorreplicación + multiplicación.
