Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
up vote 1 down vote accepted

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.

share|cite|improve this answer
G(r+j) fixes all the elements of C1 through Cj pointwise. So G(r+j-1) permutes elements of Cj through Cs, thus there may be more than k! permutations.I understand that if ab^{-1} stabilized Cj pointwise then they belong to same right coset, but how does that lead to the bound. – DurgaDatta Sep 10 '12 at 4:45
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.