¿Se puede observar cualquier grupo finito como el grupo del automorphism de un Grafo acíclico dirigido?

Question

Tenemos un grupo finito $G$, y el deseo de encontrar un DAG (dirigida gráfico acíclico) $(V,E)$ cuyo automorphism grupo es exactamente G (un gráfico automorphism de un grafo es un bijective función de $f:V\to V$ tal que $(u,v)\in E \iff (f(u),f(v))\in E$).

Una similar (positivo) para el grafo no dirigido es conocido: Frucht del teorema.

Mi incultos conjetura es que la respuesta a mi pregunta es negativa, es decir, la automorphism grupos de DAG tiene algunas propiedades especiales. Dirigida árboles que el problema es muy simple, y se puede demostrar que, incluso, $\mathbb{Z}_3$ no es realizable como el automorphism grupo de la dirigida árbol. Sin embargo, no puedo encontrar un contraejemplo para el DAG.

Answer 1

Dado un grafo no dirigido a $X=(V,E)$ con automorphism grupo $G$, de forma directa gráfico de $\hat{X}=(\hat{V},\hat{E})$, de la siguiente manera mediante el establecimiento de $$\hat{V}=V\cup\{v_e|e\in E\}$$ $$\hat{E}=\{(v,v_{\{v,w\}})|v\in V,w\in V\}.$$

Claramente cada una de las $v\in V$ cero indegree y outdegree al menos cero y cada una de las $v\in\hat{V}\setminus V$ ha indegree dos y cero outdegree. De ello se desprende que $\hat{X}$ no tiene ciclos y así es un DAG.

Debe quedar claro que cada automorphism $g$ $X$ induce un automorphism $g$ $\hat{X}$ simplemente la asignación de $v$ $g(v)$y la asignación de $v_e$$v_{g(e)}$. Debido a que el $v_{\{w_1,w_2\}}$ 'atrapados' entre los vértices $w_1$$w_2$, también debe quedar claro que no hay nuevos automorfismos puede actuar en $\hat{X}$ como la imagen de $v_{\{w_1,w_2\}}$ está totalmente determinado por las imágenes de $w_1$, $w_2$ y un posible reordenamiento de los bordes en $E$$w_1$$w_2$, que es tomado en cuenta por los de arriba inducida por la acción.

Answer 2

Deje $G=\{g_1, \ldots, g_n\}$ ser un grupo finito y deje $\alpha,\beta\notin G$. Deje $V=G\times(G\cup\{\alpha,\beta\})$ y añadir bordes de la siguiente manera: Para cada una de las $g\in G$ agregar bordes $$ (g,\alpha)\to(g,\beta)\to (g,g_1)\to\ldots\to (g,g_n)$$ y para cada una de las $g,h\in G$ agregar un borde a $(gh,\alpha)\to (h,g)$. Tenga en cuenta que los vértices $(x,\alpha)$ son precisamente aquellos con indegree $0$ e las $(x,\beta)$ son precisamente aquellos con indegree $1$. Además, solo el $(g,\alpha)$ han outdegree $>1$. De ello se deduce fácilmente que el automorphism grupo de $(V,E)$ actúa en $G\times \{\alpha\}$ y lo hace fielmente. Si un automorpshim mapas de $(g,\alpha)$ $(h,\alpha)$debe mapa de $(g,y)$ $(h,y)$todos los $y\in G\cup \{a,\beta\}$. Por último, si un autmorphism mapas de $(e,\alpha)$ $(g,\alpha)$(que tiene un borde a $(e,g)$) necesariamente debe mapa de $(h,\alpha)$ $(gh,\alpha)$porque onl ythat tiene un borde a $(h,g)$, es decir, el automorphism grupo actúa como el lado izquierdo de la multiplicación en $G\times\{\alpha\}$. Desde $(x,y)\mapsto(gx,y)$ es de hecho un automorphism de la gráfica para cada una de las $g\in G$, el automorphism grupo es isomorfo a $G$.