# Index of Automorphism groups of graphs with colour class of bounded size.

I am trying to understand group theoretic algorithms for graph isomorphism problem. In page number 64 and 65 of this book chapter, the author has bounded the index of the concerned automorphism groups (lemma 2 and 3). I really did not understand how does this statement - "if $\pi$ and $\psi \in G^{(r+j-1)}$ such that $\pi\psi^{(-1)}$ stabilizes every vertex in $C_j$ , then $\pi$ and $\psi$ lie in the same right coset of $G^{(r+j)}$"- leads to the bound in lemma 3. I found the argument in proof of lemma 2 even more confusing. Is there some standard techniques to bound the number of cosets being employed here?

Here the vertex set of graph is partitioned into $s$ colour classes each with maximum size $k$, which are to be preserved by the isomorphism. They create $\binom{s}{2} +1$ induced graphs, each having vertex set $V$, the vertex set of original graph, and starting from empty set edge set are build inductively, where at each step, edges having one vertex in class $i$ and other in class $j$ are added.

-

I had a quick look at Lemma 3. I haven't studied the notation at all, but I presume that the elements of $G^{(r+j-1)}$ permute the vertices in the set $C_j$? Since $|C_j| \le k$, there are at most $k!$ possible permutations that could be induced by elements of $G^{(r+j-1)}$. But if two such elements $\pi$ and $\psi$ induce the same permutation, then $\pi \psi^{-1}$ stabilizes all vertices in $C_j$, and hence $\pi$ and $\psi$ lie in the same right coset of $G^{(r+j)}$. So there can be at most $k!$ such right cosets, which gives the bound on the index. The argument in Lemma 2 is similar.
Because the number of cosets is at most the number of permutations of $C_j$, which is at most $k!$, because $|C_j| \le k$. – Derek Holt Sep 10 '12 at 7:55
The arguments doest not carry over exactly to lemma 2, since groups defined in lemma 2 are automorphism groups (hence set wise stabilizer of colour class) while in lemma 3 are point-wise stabiliser. I understood proof of lemma 3, but i am confused in proof of lemma 2 because even there point-wise stabilizer of $C_h \cup C_i$ are considered though the associated group is only set-wise stabilizer. – DurgaDatta Sep 10 '12 at 8:18
The permutations in $G^{(j)}$ all permute the set $C_i$ and they all permute $C_h$. Since $|C_i| \le k$ and $|C_h| \le k$, the total number of permutations of $C_h \cup C_i$ that can be induced in this way by elements of $G^{j)}$ is at most $(k!)^2$. So the argument is essentially the same as in Lemma 3. – Derek Holt Sep 10 '12 at 18:54