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!