How Graph Isomorphism is used to determine Graph Automorphism?

Question

From Lecture 2, Algebra and Computation by V. Arvind, (page2,3), I understood below passage-

For our graph $G$, let $Aut(G) = H ≤ S_n$. We shall use Weilandt’s notation where $i^\pi$ denotes the image of i under$\pi$. In this notation, composition becomes simpler: $(i^\pi)^{\tau} = i^{\pi \tau}$ Define $H_i = \{\pi ∈ H : 1^\pi = 1, 2^\pi = 2, · · · i^\pi = i \} $. And this gives the tower $H_0 = H ≥ H_1 ≥ H_2 ≥ · · · ≥ H_{n−1} = > \{e\}$ with the additional property that $[H_i : H_{i+1}] ≤ n − i $ since there are atmost $n − i$ places to go to when the first $i$ are fixed by $H_i$.

but I could not figure out -

As $H$ is $Aut(G)$, we can find the coset representatives using queries to the Graph-Iso subroutine: to find a representative for $[H_i : H_{i+1}] $, make two copies of G, force the first i vertices to be fixed (by putting identical gadgets on them in each copy), and for each place j' that i + 1 might go to, force i + 1 to go to j', test if a graph isomorphism exists, and continue till an isomorphism is found.

I could not follow the argument!

Questions:

1. What is the meaning of "putting identical gadgets on them in each copy", in particular, what does "gadgets " mean?

2. How Isomorphism is used to find coset representatives? or what does the following passage mean?

for each place j' that i + 1 might go to, force i + 1 to go to j', test if a graph isomorphism exists, and continue till an isomorphism is found.

Thanks.

Answer 1

Putting identical gadgets on the vertices in each copy means you add some characteristic so that, in an isomorphism from one copy to the other, you force a particular vertex to get mapped to a specific other vertex.

For example, say we have two copies of $K_{5}$, vertices labelled identically $1,2,3,4,5$, and I want an isomorphism fixing $1$. Then in each copy, I will add another edge to vertex $1$ (going to a new vertex I don't care about). Now when I construct my isomorphism, vertex $1$ has to be fixed (slight abuse of terminology, really this is saying vertex $1$ in the first copy is forced to go to vertex $1$ in the second copy) because in each graph, it is the unique vertex of degree $5$ while all others have degree $4$ (aside from our new throwaway vertex with degree $1$).

What they actually mean by saying they need to "find a representative for $[H_{i}:H_{i+1}]$" is, they need to find a collection of representatives $\{ a_{1}, \ldots, a_{s}\}$ so that $$H_{i} = a_{1}H_{i+1} \cup \ldots \cup a_{s}H_{i+1}.$$ In both subgroups $H_{i}$ and $H_{i+1}$, the first $i$ vertices are fixed. So you really need just one automorphism sending vertex $i+1$ to every possible place it can go. You can do this by attaching appropriate "gadgets" and then calling your algorithm to test isomorphism. So for example you attach an appropriate gadget to the first $i$ vertices in both graphs to ensure they are fixed. Then you attach a new unique gadget to the $(i+1)$st vertex in the first copy and the $j$th vertex in the second copy and test isomorphism; if you get an isomorphism, it will correspond to an automorphism of your original graph fixing the first $i$ vertices and sending vertex $i+1$ to $j$. You do this for each $j \in \{i+1, \ldots, n\}$. The collection of automorphisms you get will be your set of representatives for $[H_{i}:H_{i+1}]$.

Answer 2

Try reading Mathon's paper (pages 1 - 2):

http://www.sciencedirect.com/science/article/pii/0020019079900048

It should be explained there more clearly.

Answer 3

An explanation(Not a proof):

Let, $F_1$ and $F_2$ are 2 copies of $G$.

Keep first $i$ vertices fixed in both $F_1$ and $F_2$. You do not need to overthink gadgets, it is not essential to understand the proof, it is required for implementation. Just consider that first $i$ vertices are fixed.

By definition, $H_{i+1} \leq H_{i}$, and $H_i$ is a group of automorphisms for $G$(thus, for $F_1, F_2$ also) where $1\leq i\leq n$.

Now, Without Loss of Generality, consider a transposition,$\pi$ that moves $(i+1)$ th vertex to $j'$ th position where $i <j'\leq n$. Definiltely, $\pi \notin H_{i+1}$. So, $\pi$ could be a Coset Representative (not yet) .

If, $\pi$ is an automorphism of $F_2$, then $\pi$ is a Coset Representative Since the right coset $H_{i+1} \pi$ is a set automorphism for $F_2$. By definition, $H_{i+1} \pi \subseteq H_i$ and $H_i$ is made of all such cosets.

So, to construct $H_i$, you have to find all Coset Representative . How you find them? You apply $\pi$ that moves $(i+1)$ th vertex to $j'$ th position where $i <j'\leq n$ on $F_2$. If $F_2^{\pi}$ is isomorphic to $F_1$, then $\pi$ is an automorphism of $F_2$. You need 2 copies of $G$, $F_1$ and $ F_2$ for implementation of the algorithm that finds Coset Representative since once you apply $\pi$ on $F_2$, you do not see how it looked before applying $\pi$ , so you need a copy of $G$ or $F_1$ to compare or to test. Note that, you are finding an automorphism through isomorphism test.

Addition(after Morgan Rodgers' comment): "Gadget" is required for implementation. Above , I tried to explain what "Gadget" does rather than explaining what it is.