# Confusion about the hidden subgroup formulation of graph isomorphism

I am going through Quantum factoring, discrete logarithms and the hidden subgroup problem by Richard Jozsa. On page 13, the author discussed the hidden subgroup problem (HSP) formulation of the graph isomorphism (GI) problem. I would like to make it sure that I get the development of the concept right.

Here both $A$ and $B$ are graphs of $n$-vertices. In each case, the vertices are labeled from $1$ to $n$. $M_A$ and $M_B$ are their adjacency matrices respectively. $\mathcal{P}_n$ is the permutation group of $n$ symbols. $C$ is the disjoint union of $A$ and $B$. So, it is a graph of $2n$ vertices labeled $1 \ldots n, n+1 \ldots 2n$.

In the 5th paragraph of page 13, it is said that,

The symmetry group $K$ of $C$ is evidently a subgroup of $\mathcal{P}_{2n}$ but we can say more: since $A$ and $B$ are connected and $C$ is the disjoint union, any symmetry of $C$ must either separately permute the sets of labels $L_A = \left\{1, 2, . . . , n\right\}$ and $L_B = \left\{n + 1,...,2n\right\}$ or else swap the two sets entirely. Thus if $H$ denotes the group $\mathcal{P}_n \times \mathcal{P}_n$ and $\sigma$ is the permutation of $1,2, \ldots ,2n$ that swaps the two sets $S_A$ and $S_B$ in their listed order, then $K$ will always be a subset of the group $G = H ∪ \sigma H$.

I understand that $|H| = |\mathcal{P}_n \times \mathcal{P}_n| = n^2$. If we define $\sigma$ as a swap operation over $H$ so that it separately permutes $A$ and $B$ as they are in $C$, $\sigma$ has to deal with $n^2$ symbols while only $2n$ of them get swapped keeping the position of the rest unchanged. This permutation maintains the listed order as the author says.

1. Where does this listed order come from? Is it just the ordered pair of vertices from the two input graphs, $A$ and $B$?
2. I understand that a listed order is the list or ordered pairs which remains intact after the permutation. Shouldn't a list of ordered pairs of vertices from $\left(A, B\right)$ be preserved for any permutation over $2n$ symbols?
3. Moreover, isn't $\sigma$ an element of a group which is of order 2?
4. Finally, why $K$ will always be a subset of the group $G = H \cup \sigma H$ ?

For reference the rest of the paragraph is:

$H$ is the subgroup of $G$ containing all permutations that map $S_A$ and $S_B$ into themselves whereas $\sigma H$ is its one other coset, of all permutations that swap the elements of $S_A$ and $S_B$ (in some arbitrary order). Now we may easily verify the following facts:

1. if $A$ and $B$ are not isomorphic then $K$ lies entirely in $H$,
2. if $A$ and $B$ are isomorphic then exactly half of the members of $K$ are in $H$ and half are in $\sigma H$.

$(1)$ The listed order doesn't come from anywhere, we put it there at the beginning. The vertices of the graph $C$ are $\{1,\cdots,n\}$ (the ones belonging to $A$) and $\{n+1,\cdots,2n\}$ (belonging to $B$); anything enumerated by naturals and written down in order is automatically a listed order.
$(2)$ I think "listed order" just means "listed order," with no special technical meaning. The edge sets of $A$ and $B$ are each collections of ordered pairs of vertices, we combine these collections (after relabelling the vertices and edges in $B$ appropriately) to get the edge set of $C$. The symmetries in $K$ are certainly supposed to preserve the edge set of $C$. So if $\sigma$ is the permutation of $\{1,\cdots,2n\}$ which sends $i\mapsto i+n$ for $1\le i\le n$ and sends $j\mapsto j-n$ for $n<j\le 2n$ then $\sigma$ may not preserve the edge set of $C$, hence $\sigma$ may not be an element of $K$. We are not assuming that it is.
$(3)$ Yes, $\sigma$ is an involution (meaning $\sigma=\sigma^{-1}$ or $\sigma^2=e$) so $\langle\sigma\rangle=\{e,\sigma\}$ is a group of order $2$ which contains the permutation $\sigma$. This doesn't really seem very relevant.
$(4)$ We've already observed any symmetry in $K$ preserves the partition $\{A,B\}$ of $C$s vertex set; the set of all permutations preserving this partition is $H\cup\sigma H$ (hence $K\subseteq H\cup\sigma H$ follows). Let $\tau$ be any permutation in ${\cal P}_{2n}$ preserving this partition. Either $\tau(A)=A$ and $\tau(B)=B$ (no swapping occurs) and hence $\tau\in{\cal P}_n\times{\cal P}_n=H$, or else $\tau(A)=B$ and $\tau(B)=A$ (swapping occurs). Notice that the permutations preserving the partition $\{A,B\}$ are closed under inverses and composition so it is a subgroup $S$, and $\sigma$ is an element of $S$ just like $\tau$. We know $\sigma(A)=B$ and $\sigma(B)=A$, and we also know $\sigma^{-1}\circ\tau\in S$. Furthermore, $(\sigma^{-1}\circ\tau)(A)=A$ and $(\sigma^{-1}\circ\tau)(B)=B$, so $\sigma^{-1}\circ\tau$ is an element of ${\cal P}_n\times{\cal P}_n=H$, and so $\sigma^{-1}\tau\in H\implies \tau\in\sigma H$. Thus, $S\subseteq H\cup\sigma H$ and the reverse inclusion is clearly true, so $S=H\cup\sigma H$.
• at the bottom of page 13 it says, "Given any element $\Pi \in G$ it is easy to check whether it lies in $H$ or $\sigma H$". This looks confusing. I thought $\Pi$ works on $n$ items while any element of $G$ should work on $2n$ items. – Omar Shehab Jun 24 '14 at 18:21
• @OmarShehab We can reuse letters in math. Previously the author began a claim with "if there exists a $\Pi\in{\cal P}_n$ ..." in that claim, indeed $\Pi$ only operates on $n$ items. However in the paragraph you're quoting, it reboots the usage of that letter with "Given any element $\Pi\in G$," which automatically means $\Pi$ is some element of $G$ by definition in that new context. – blue Jun 24 '14 at 18:42