0
$\begingroup$

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.

1 Answers 1

1

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.

  • 0
    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.2012-09-10