Frucht del Teorema establece que para cualquier finito grupo $G$ hay un número finito (no dirigido) gráfico $\Gamma$ para que el automorphism grupo $\text{Aut}(\Gamma)$ de $\Gamma$ es isomorfo a $G$, y para muchos grupos pequeños de $G$ no es difícil construir un pequeño gráfico de $\Gamma$ cuya automorphism grupo $\text{Aut}(\Gamma)$ es isomorfo a $G$.
Por ejemplo, $\Bbb Z_1$, $\Bbb Z_2$, y $S_3$ son los automorphism grupos de la completa de los gráficos de $K_1, K_2$, $K_3$, respectivamente, $\Bbb Z_2 \times \Bbb Z_2$ es el automorphism grupo de
,
$\Bbb Z_3$ es el automorphism grupo de los $9$-vértice de la gráfica
,
$\Bbb Z_4$ y $\Bbb Z_5$ son, respectivamente, el automorphism grupos de los $12$ y $15$-vértice análogos de que la gráfica dada (de manera informal) reemplazando el triángulo central con un cuadrado o un pentágono, $\Bbb Z_6$ es el automorphism grupo de los $12$-vértice de la gráfica
,
y $\Bbb Z_7$, $\Bbb Z_8$ y $\Bbb Z_9$ son, respectivamente, el automorphism grupos de la $14$-, $16$-, y $18$-vértice análogos de que la gráfica dada por la sustitución de los hexágonos con heptagons, octógonos, y nonagons.
Esto representa para todos los grupos de orden $< 10$ (de hecho, excepto para el ejemplo de $\Bbb Z_4$, estos ejemplos son todos un mínimo de w.r.t. el número de vértices, al menos entre las gráficas), excepto $\Bbb Z_2 \times \Bbb Z_2 \times \Bbb Z_2$, $\Bbb Z_3 \times \Bbb Z_3$, y los cuaterniones $8$grupo, $Q_8$. Uno puede modificar sin mucho alboroto de los ejemplos de arriba para elaborar gráficos con automorphism grupos de la abelian grupos en esta lista, pero no es tan claro (para mí) para ver cómo se construye una razonablemente pequeño gráfico con automorphism grupo $Q_8$:
¿Cuál es el mínimo número de vértices de un grafo $\Gamma$ que $\text{Aut}(\Gamma) \cong Q_8$? ¿Qué es un ejemplo de una gráfica que alcanza este mínimo? Entre los gráficos de este tipo, que haya (n) el número mínimo de aristas?
Nos puede dar una cota superior para el número de vértices: Un teorema de Babai dice para todos los grupos, $G \no\cong \Bbb Z_3, \Bbb Z_4, \Bbb Z_5$ no hay un gráfico de $\Gamma$ $\text{Aut}(\Gamma)$ tal que la acción de la automorphism grupo tiene sólo dos órbitas, y así, en particular, tiene un número de vértices $V(\Gamma)$ de no más de $2|G|$; por lo tanto, no hay un gráfico de $\Gamma$ $\text{Aut}(\Gamma) \cong Q_8$ y $V(\Gamma) \leq 16$. (Espero que $16$ es la mínima alcanzable.)
Se puede intentar resolver esto a través de la explotación de una constructivo prueba de Frucht del Teorema: Aproximadamente, uno empieza con un grafo de Cayley de $G$ (que se dirige y el color según el generador), que ha automorphism grupo (de indicaciones, de color de los gráficos) $G$. Luego, se reemplaza cada borde con un adecuado (no dirigido) gráfico, la elección de una sustitución distintas gráfico para cada generador, para evitar la introducción de nuevas simetrías.
No está claro, sin embargo, que este enfoque puede producir un gráfico con $\leq 16$ vértices y automorphism grupo $Q_8$. El más simple de Cayley gráfico de $Q_8$ es
,
pero esto ya tiene $16$ bordes, y es difícil ver cómo se podía sustituir ellos sin la adición de más de $8$ nuevos vértices en total.
Esta respuesta, por cierto, le da un gráfico con $32$ los vértices con automorphism grupo $Q_8$ (actuando con $4$ órbitas en el gráfico):
.
Por cierto, uno puede usar el método anterior para mejorar este resultado, es decir, la construcción de un gráfico de $\Gamma$ con $< 32$ vértices y automorphism grupo $Q_8$: Dejar $S(p, q)$ denotar el gráfico con tres vértices $a, b, c$, $p$ bordes entre $a$ y $b$ y $q$ bordes entre $b$ y $c$. Entonces, podemos sustituir las flechas rojas en la anterior Cayley gráfico con $S(p, q)$ (debidamente orientado a), y las flechas verdes con $S(p', q')$, donde $p, p, p', q'$ son elegidos para evitar la introducción de nuevas automorfismos. Cada reemplazo añade un vértice, por lo que el gráfico resultante tiene $24$ vértices. (Este gráfico es, sin embargo, no es sencillo, y lo es menos que todo satisfactoria.)
Babai, L., "Sobre el pedido mínimo de gráficos con determinado grupo." Canadá. De matemáticas. Bull., 17, pp 467-470, 1974.
Frucht, R., "Herstellung von Graphen mit vorgegebener abstrakter Gruppe." De naturaleza Mathematica (en alemán) 6, pp 239-250, 1939.
