Conde de Hoffman-Singleton

Conde de Hoffman-Singleton

Lleva el nombre de	Alan Hoffman Robert R. Singleton
picos	cincuenta
costillas	175
Radio	2
Diámetro	2 [1]
Circunferencia	5 [1]
automorfismos	252.000 ( fuente de alimentación(3.5 2 ):2) [2]
Número cromático	cuatro
índice cromático	7 [3]
Género	29 [4]
Propiedades	Gráfico de Moore de jaula de enteros hamiltonianos simétricos fuertemente regulares
Archivos multimedia en Wikimedia Commons

El gráfico de Hoffman-Singleton es un gráfico no dirigido homogéneo de 7 con 50 vértices y 175 aristas. El gráfico es el único gráfico fuertemente regular con parámetros [5] . El gráfico fue construido por Alan Hoffman y Robert Singleton cuando 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 el gráfico es un gráfico de Moore , en el que cada vértice tiene un grado 7 y la circunferencia del gráfico es 5, el gráfico es una celda . ${\ estilo de visualización (50,7,0,1)}$ ${\ estilo de visualización (7,5)}$

Edificio

Hay muchas formas de construir gráficos de Hoffman-Singleton.

Construcción basada en pentágonos y pentagramas

Tomemos 5 pentágonos y 5 pentagramas para que el vértice del pentágono sea adyacente a los vértices de y el pentágono y el vértice del pentagrama sea adyacente a los vértices de y el pentagrama . Conectemos la parte superior del gráfico con la parte superior del gráfico . (Todos los índices se toman módulo 5.) ${\ estilo de visualización P_ {h}}$ $Q_{yo}$ $j$ ${\ estilo de visualización P_ {h}}$ $j-1$ $j+1$ ${\ estilo de visualización P_ {h}}$ $j$ $Q_{yo}$ ${\ estilo de visualización j-2}$ ${\ estilo de visualización j+2}$ $Q_{yo}$ $j$ ${\ estilo de visualización P_ {h}}$ $h\bullet {i}+j$ $Q_{yo}$

Construcción a partir de trillizos y planos Fano

Tome un avión Fano y considere permutar sus 7 puntas para obtener 30 aviones Fano. Elijamos uno de estos aviones. Hay otros 14 aviones Fano que tienen exactamente una triple ("línea") común con el avión elegido. Tome estos 15 aviones Fano y deseche los 15 restantes. Considere 7 C 3 = 35 tripletes de 7 números. Ahora conectamos (mediante un borde) un triple con los planos de Fano que contienen este triple, y también conectamos triples que no se intersecan entre sí. El grafo resultante es un grafo de Hoffman-Singleton, consta de 50 vértices correspondientes a 35 tripletes y 15 planos de Fano, y cada vértice tiene grado 7. Los vértices correspondientes a los planos de Fano están conectados a 7 tripletes por definición, ya que el plano de Fano tiene 7 líneas. Cada terna está asociada a 3 planos diferentes de Fano que lo incluyen, ya otras 4 ternas con las que no se cruza.

Propiedades algebraicas

El grupo de automorfismos del grafo de Hoffman-Singleton es un grupo de orden 252000 y es isomorfo a PΣU(3,5 2 ), el producto semidirecto del grupo unitario especial proyectivo $fuente de alimentación(3,5^{2})$ y el grupo cíclico de orden 2 generado por el endomorfismo de Frobenius . Un automorfismo actúa transitivamente sobre los vértices y las aristas de un gráfico. Por lo tanto, el gráfico de Hoffman-Singleton es un gráfico simétrico . El estabilizador de vértice del gráfico es isomorfo al grupo simétrico de 7 letras. El estabilizador del juego de bordes es isomorfo a , donde hay un grupo alterno de 6 letras. Ambos tipos de estabilizadores son subgrupos máximos del grupo de automorfismos completo del gráfico de Hoffman-Singleton. $S_7$ $Aut(A_{6})=A_{6}\cdot 2^{2}$ $A_{6}$

El polinomio característico del gráfico de Hoffman-Singleton es . Por lo tanto, el gráfico de Hoffman-Singleton es entero : su espectro consiste completamente en números enteros. ${\ estilo de visualización (x-7) (x-2) ^ {28} (x + 3) ^ {21}}$

Subgrafos

Usando solo el hecho de que el gráfico de Hoffman-Singleton es estrictamente regular con parámetros , podemos mostrar que hay 1260 ciclos de longitud 5 en él. ${\ estilo de visualización (50,7,0,1)}$

Además, el Conde Hoffman-Singleton contiene 525 copias del Conde Petersen . Al eliminar uno de ellos, se obtiene una copia de la única celda [ 7] . ${\ estilo de visualización (6,5)}$

Véase también

Tabla de gráficos más grandes conocidos de diámetro dado y grado máximo

Notas

↑ 1 2 Weisstein, Eric W. Hoffman-Singleton Gráfico en el sitio web Wolfram MathWorld .
↑ Hafner, 2003 , pág. 7-12.
↑ Royle .
↑ Conder, Stokes, 2014 .
↑ Navegador .
↑ Hoffman, Singleton, 1960 , pág. 497–504.
↑ Wong, 1979 , pág. 407–409.

Literatura

PR Hafner. El gráfico de Hoffman-Singleton y sus automorfismos // J. Combinación algebraica. - 2003. - T. 18 .
G.Royle. Re: ¿Cuál es el número cromático de borde de Hoffman-Singleton? . Publicación de [email protected]. (28 de septiembre de 2004). (indefinido) (enlace no disponible)
MDE Conder, K. Stokes. Incrustaciones mínimas de género del gráfico de Hoffman-Singleton // preprint. — 2014.
CT Benson, NE Losey. En un gráfico de Hoffman y Singleton // Journal of Combinatorial Theory. Serie B. - Vol. 11 , núm. 1 . — S. 67–79 . — ISSN 0095-8956 . - doi : 10.1016/0095-8956(71)90015-3 .
D. A. Holton, J. Sheehan. El Petersengraph . - Cambridge University Press , 1993. - S. 186 , 190. - ISBN 0-521-43594-3 . .
Andries E. Brouwer. Gráfico de Hoffman-Singleton . Consultado el 7 de septiembre de 2016. Archivado desde el original el 3 de marzo de 2016. (indefinido)
Alan J. Hoffman, Robert R. Singleton. Gráficos de Moore con diámetro 2 y 3 // IBM Journal of Research and Development. - 1960. - V. 5 , núm. 4 . — S. 497–504 . -doi : 10.1147/ rd.45.0497 .
Pak-Ken Wong. Sobre la unicidad del gráfico más pequeño de circunferencia 5 y valencia 6 // Journal of Graph Theory. - 1979. - T. 3 . — S. 407–409 . -doi : 10.1002 / jgt.3190030413 .