Actuar de permutación de aristas inducidas por permutación actuando en los vértices

Question

De "Lecture Notes in Computer Science" por Christoph M. Hoffmann

Deje $X = (V,E)$ ser un grafo con conjunto de vértices $ V = \{1,2..... n \} $. El automorphism grupo $Aut(X)$ $X$ es un subgrupo de $S_n$. Weconstruct una nueva representación para $S_n$ por dejar que el grupo actúe en el conjunto de todos los pares no ordenados $(i,j)$; $ 1 \leq i,j \leq n, i \neq j$. El grupo de isomorfismo llevar a cabo esto es definido por el asociación de $\pi$ $S_n$ con una permutación $\psi$ de la nueva permutación de dominio, donde $(i,j)^{\psi} = (i^{\pi},j^{\pi})$ Deje $S_n'$ denotar $S_n$ actuando en esta nueva permutación de dominio. Nota que $S_n$ es generado por los dos permutaciones $\alpha = (1,2)$, y $\beta = (1,2 .... , n)$. Así también contamos con generadores de $S_n'$ . Deje $E$ el conjunto de no-bordes de $X$, es decir, la desordenada par $(i,j)$ $ E$ fib $(i,j)$ no $\bar E$. Vamos $T = Sym(E)×Sym(\bar E)$ ser el producto directo de $Sym(E)$ y $Sym(\bar E)$. Tenga en cuenta que $T$ es generado por cuatro permutaciones que sabemos. Reclamamos el siguiente

Teorema 7

Deje $X = (V,E)$ ser un grafo con conjunto de vértices $V = \{1,2 ..... n \}$. A continuación, $Aut(X)$ es isomorfo a la intersección de las $S_n'$ con $T =Sym(E) \times Sym(\bar E)$. Prueba: Vamos a $A = Aut(X)$ ser el automorphism grupo de $X, A'$ la isomorfo >grupo obtiene dejando $A$ actúan en el conjunto de todos los no ordenados de vértices pares. Deje $\alpha \in A $ ser un automorphism, $\alpha'$ el elemento correspondiente en $A'$. Desde $\alpha$ es un vértice de permutación, $\alpha'$ es un elemento de $S_n'$. Desde $\alpha$ los mapas de bordes en los bordes y nonedges en nonedges, $\alpha'$ es también en $T$. Por el contrario, vamos a $\alpha'$$S_n' \cap T$. Desde $\alpha' \in S_n'$ , es asociada a una permutación de vértices en $S_n$. Desde $\alpha' \in T$, el correspondiente vértice de permutación de los mapas de bordes en bordes y nonedges en nonedges, por lo tanto es un automorphism. Por lo tanto, $A' = S_n' \cap T$ .

No entiendo el paso-

Construimos una nueva representación para $S_n$ por dejar que el grupo actúe en el conjunto de todos los pares no ordenados $(i,j)$; $ 1 \leq i,j \leq n, i \neq j$.

Desordenada pares refiero a todos los de la posible falta de aristas y los bordes de las $X$.

El grupo de isomorfismo llevar a cabo esto es definido por el asociación de $\pi$ $S_n$ con una permutación $\psi$ de la nueva permutación de dominio, donde $(i,j)^{\psi} = (i^{\pi},j^{\pi})$.

Esto significa edge/no-edge $(i,j)$ se asigna a $(i,j)^{\psi}$ (por permutación $\psi$)cuando los vértices $i^{},j^{}$ son asignadas a $i^{\pi},j^{\pi}$ (por permuation $\pi$)

Deje $S_n'$ denotar $S_n$ actuando en esta nueva permutación de dominio.

¿Significa esto $S_n'$ es el grupo simétrico de todas las aristas y los bordes no de $X$?

En ese caso debería ser$S_{{n}\choose{2}}'$ en lugar de $S_n'$ .

También , se $A'=T \leq S_n'$ ? desde

Desde $\alpha$ mapas de bordes en los bordes y no de los bordes en la no-bordes, $\alpha'$ $T$.

Además, ¿cuál es el significado del teorema? Yo realmente no lo entiendo!

Answer 1

Creo que hay un montón de no entender, incluso en el primer párrafo. Yo podría ser capaz de explicar parte de ella.

Supongamos $G$ es un grupo de automorfismos de un gráfico de $X=(V,E)$. A continuación, $G$ es una permutación grupo que actúe en $V$. Si nos ponemos a pensar, vemos que, para cada una de las $k\ge1$, $G$ permutar el conjunto $\binom{V}{k}$ de todos los subconjuntos de a $V$. Por lo tanto, tenemos un homomorphism de la permutación grupo $G$ a un grupo de permutación $H$ actuando en $\binom{V}{k}$, para cada una de las $k$. [El término "homomorphism" está siendo abusado aquí, hay más estructura que debe ser preservado.]

A menudo, $G$ $H$ va a ser isomorfo como resumen de los grupos. (Pero si $k=2$$X=K_2$, no existen.)

Supongamos ahora que $k=2$. A continuación, $H$ actúa sobre los pares no ordenados de vértices de $X$. Si $X$ es completo ni vacío, el conjunto de pares no ordenados pueden dividir en dos celdas no vacías $E$ $\bar{E}$ donde$E=E(X)$$\bar{E}=E(\bar{X})$. Tanto en $E$ $\bar{E}$ son los sindicatos de órbitas de $H$ se $H$-invariante.

Si $H$ es una permutación de un grupo sobre un conjunto $S$ y este conjunto es distinto de la unión de dos $H$-invariante subconjuntos $C$$D$, $H$ puede ser expresado como subgrupo del producto directo de dos grupos de permutación, es decir, las restricciones de $H$ $C$ $D$respectivamente. Por lo tanto, $H$ es isomorfo a un subgrupo de $\mathrm{Sym}(C)\times\mathrm{Sym}(D)$.