4
$\begingroup$

From "Lecture Notes in Computer Science" by Christoph M. Hoffmann

Let $X = (V,E)$ be a graph with vertex set $ V = \{1,2..... n \} $. The automorphism group $Aut(X)$ of $X$ is a subgroup of $S_n$. Weconstruct a new representation for $S_n$ by letting the group act on the set of all unordered pairs $(i,j)$; $ 1 \leq i,j \leq n, i \neq j$. The group isomorphism accomplishing this is defined by the association of $\pi$ in $S_n$ with a permutation $\psi$ of the new permutation domain, where $(i,j)^{\psi} = (i^{\pi},j^{\pi})$ Let $S_n'$ denote $S_n$ acting on this new permutation domain. Note that $S_n$ is generated by the two permutations $\alpha = (1,2)$, and $\beta = (1,2 .... , n)$. Thus we also have generators for $S_n'$ . Let $E$ be the set of non-edges of $X$, that is, the unordered pair $(i,j)$ is in $ E$ iff $(i,j)$ is not in $\bar E$. Let $T = Sym(E)×Sym(\bar E)$ be the direct product of $Sym(E)$ and $Sym(\bar E)$. Note that $T$ is generated by four permutations which we know. We claim the following

Theorem 7

Let $X = (V,E)$ be a graph with vertex set $V = \{1,2 ..... n \}$. Then $Aut(X)$ is isomorphic to the intersection of $S_n'$ with $T =Sym(E) \times Sym(\bar E)$. Proof: Let $A = Aut(X)$ be the automorphism group of $X, A'$ the isomorphic >group obtained by letting $A$ act on the set of all unordered vertex pairs. Let $\alpha \in A $ be an automorphism, $\alpha'$ the corresponding element in $A'$. Since $\alpha$ is a vertex permutation, $\alpha'$ is an element of $S_n'$. Since $\alpha$ maps edges into edges and nonedges into nonedges, $\alpha'$ is also in $T$. Conversely, let $\alpha'$ be in $S_n' \cap T$. Since $\alpha' \in S_n'$ , there is an associated vertex permutation in $S_n$. Since $\alpha' \in T$, the corresponding vertex permutation maps edges into edges and nonedges into nonedges, hence it is an automorphism. Therefore, $A' = S_n' \cap T$ .

I don't understand the the passage-

We construct a new representation for $S_n$ by letting the group act on the set of all unordered pairs $(i,j)$; $ 1 \leq i,j \leq n, i \neq j$.

Unordered pairs mean all possible non-edges and edges of $X$.

The group isomorphism accomplishing this is defined by the association of $\pi$ in $S_n$ with a permutation $\psi$ of the new permutation domain, where $(i,j)^{\psi} = (i^{\pi},j^{\pi})$.

This means edge/non-edge $(i,j)$ is mapped to $(i,j)^{\psi}$ (by permutation $\psi$)when vertices $i^{},j^{}$ are to mapped to $i^{\pi},j^{\pi}$ (by permuation $\pi$)

Let $S_n'$ denote $S_n$ acting on this new permutation domain.

Does this mean $S_n'$ is the symmetric group of all edges and non edges of $X$?

In that case it should be$S_{{n}\choose{2}}'$ instead of $S_n'$ .

Also , is $A'=T \leq S_n'$ ? since

Since $\alpha$ maps edges into edges and non-edges into non-edges, $\alpha'$ is also in$T$.

Besides, what is the significance of the theorem? I really don't get it!

$\endgroup$
5
$\begingroup$

I think there's a lot not to understand in even the first paragraph. I might be able to explain part of it.

Suppose $G$ is a group of automorphisms of a graph $X=(V,E)$. Then $G$ is a permutation group acting on $V$. If we think about we see that, for each $k\ge1$, our group $G$ will permute the set $\binom{V}{k}$ of all subsets of $V$. Hence we have a homomorphism from the permutation group $G$ to a permutation group $H$ acting on $\binom{V}{k}$, for each $k$. [The term "homomorphism" is being abused here, there is extra structure that must be preserved.]

Often $G$ and $H$ will be isomorphic as abstract groups. (But if $k=2$ and $X=K_2$, there are not.)

Assume now that $k=2$. Then $H$ acts on the unordered pairs of vertices of $X$. If $X$ is neither complete nor empty, the set of unordered pairs can partitioned into two non-empty cells $E$ and $\bar{E}$, where $E=E(X)$ and $\bar{E}=E(\bar{X})$. Both $E$ and $\bar{E}$ are unions of orbits of $H$, they are $H$-invariant.

If $H$ is a permutation group on a set $S$ and this set is the disjoint union of two $H$-invariant subsets $C$ and $D$, then $H$ can be expressed as subgroup of the direct product of two permutation groups, namely the restrictions of $H$ to $C$ and $D$ respectively. Therefore $H$ is isomorphic to a subgroup of $\mathrm{Sym}(C)\times\mathrm{Sym}(D)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.