Dejemos que $G$ sea un gráfico en $r$ vértices $\{1,2,\ldots,r\}$ . Denota además $H$ para ser el subgrafo de $G$ inducido por los vértices $\{1,2,\ldots,(r-1)\}$ . Denote $Aut(G)$ y $Aut(H)$ para ser el grupo de automorfismo de los gráficos $G$ y $H$ respectivamente. ¿Es cierto que $$ |Aut(G)| \le r |Aut(H)|, $$ o incluso $$ |Aut(G)| \le C r |Aut(H)|, $$ para alguna constante universal $C$ ?
Respuestas
¿Demasiados anuncios?
Keltia
Puntos
8104
Tome $X$ para ser un gráfico de Paley en $q$ vértices. Entonces $|\mathrm{Aut}(X)\ge q(q-1)/4$ . Pero $X$ contiene, como subgrafos inducidos, todos los grafos finitos en algo así como $\log(q)$ vértices (Bollobas y Thomason); en particular tiene subgrafos asimétricos de este orden.
Para otra familia de ejemplos tomemos un grupo $G$ que admite un grafo de Cayley $X$ tal que $\mathrm{Aut}(X)\cong G$ . (La llamada representación gráfica de $G$ (también conocido como GRR). Entonces el subgrafo de $X$ que obtenemos al eliminar un vértice es asimétrico. Los grupos finitos de orden mayor que 32 que no son abelianos con exponente mayor que dos, o díctilos generalizados, siempre tienen un GRR.
La respuesta a tu primera pregunta es sí, esto se deduce del teorema del estabilizador orbital. Si H es el subgrafo obtenido al eliminar el vértice $v$ entonces $Aut(H)$ contendrá una copia del estabilizador de vértices $Aut(G)_v$ (aunque puede ser mayor). Por el teorema del estabilizador de la órbita, $|Aut(G):Aut(G)_v|\leq r$ y el resultado es el siguiente.
