El gráfico de 21 vértices de Gordon Royle

Question

OEIS A080803 enumera el número mínimo de vértices $a(n)$ necesario para soportar un grafo no dirigido cuyo grupo de automorfismo tiene orden $n$ . La página de MathWorld sobre automorfismos del grafo enlaza con esta secuencia y reproduce la lista, pero hay una discrepancia: MathWorld da 23 vértices para 21 automorfismos, OEIS da 21.

Este último valor, más pequeño, lo explica Jens Voß:

El valor $\text{A080803}(21)=21$ se debe a Gordon Royle, que encontró un grafo con 21 vértices cuyo grupo de automorfismo es no abeliano de orden 21 (un subgrupo 2'-Hall del grupo $\text{PSL}_2(7)$ ).

Sin embargo, no se proporciona ninguna referencia al respecto.

¿Cómo es exactamente el gráfico de 21 vértices de Royle?

Sólo hay un grupo no abeliano de orden 21, $\mathbb Z_7\rtimes\mathbb Z_3$ uno de cuyos grafos de Cayley se muestra a continuación (tomado de Lista de bodas ):

Como dirigido gráfico, éste tiene efectivamente 21 automorfismos. Sin embargo, la eliminación de las orientaciones de las aristas permite reflejar el gráfico, lo que eleva el número de automorfismos a 42. Entonces, ¿cuál era el gráfico que encontró Royle?

Answer 1

Una búsqueda de fuerza bruta revela que la valencia más pequeña de un ejemplo es $8$ . (Estoy asumiendo que el gráfico es transitivo por vértices).

He aquí un ejemplo. Dejemos que $a$ sea un elemento de orden $3$ en el grupo, y $b$ y elemento de orden $7$ . Entonces toma $S=\{a^2b^2,a^2,a^2b^3,b^4\}$ y luego tomar el gráfico de Cayley con respecto a $S\cup S^{-1}$ .

Answer 2

El gráfico que Royle encontró, que llamaré el 21-21 gráfico para su orden y recuento de automorfismos, puede construirse mediante el enfoque del grafo de Cayley expuesto en la otra respuesta de la siguiente manera:

• El conjunto de vértices es $\{(a,b):0\le a<3,0\le b<7\}$ .
• Una séptima parte del conjunto de bordes $E(n)$ es la unión de los tres conjuntos siguientes, donde los segundos índices de cada vértice se toman en módulo 7: $$\{((0,n),v):v\in\{(1,n),(0,n+3),(1,n-3),(1,n-1)\}\}\\ \{((1,n),v):v\in\{(2,n),(1,n+1),(2,n+1),(2,n-2)\}\}\\ \{((2,n),v):v\in\{(0,n),(2,n+2),(0,n+2),(0,n+3)\}\}$$ El conjunto de bordes es entonces la unión de los $E(n)$ para $0\le n<7$ .

Esto crea un grafo 8-regular con 84 aristas que puede dividirse en cuatro circuitos de 21 aristas, uno de los cuales es un ciclo hamiltoniano. El código de graph6 para este grafo es TyTXPSjxOI_jfI_IoDWfIC@VoDWCxVC@S]?j .

El código de SageMath que confirma que este gráfico tiene 21 automorfismos, así como las fuentes SVG para las imágenes anteriores, se pueden encontrar aquí .