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$

1 Answer 1

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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .