<p>If you're interested in the group theory that's relevant for Graph Isomorphism, then in addition to Seress's book that David Eppstein mentioned, I would highly recommend</p>

<blockquote>
  <p>Dixon and Mortimer's <a href="http://www.ams.org/mathscinet-getitem?mr=1409812" rel="noreferrer">Permutation Groups</a></p>
</blockquote>

<p>The above is a book on "just" group theory, but of the books on pure group theory, it is probably the most relevant to Graph Isomorphism.</p>

<p>A book that is more directly about algorithms for graph isomorphism, which puts group-theoretic algorithms at center stage, is:</p>

<blockquote>
  <p>Christoph Hoffman. <a href="http://dx.doi.org/10.1007/3-540-11493-9/" rel="noreferrer">Group-theoretic algorithms and graph isomorphism</a>. Springer Lecture Notes in Computer Science 136.</p>
</blockquote>

<p>The latter (together with Paolo Codenotti's thesis) is currently one of the few widely accessible places where you can really find a complete account of some of the more group-theoretic algorithms for graph isomorphism.</p>

CC BY-SA 4.0
2021-08-15T15:41:04.290Z
Hi! I can't ask questions that are not related to research, I am requesting you to respond to following questions related to Paolo's thesis: 
Page 35 the author writes, "Let $B_1 \cdots B_k$ be a minimal system of imprimitivity (maximal blocks) of the $G$-action on **one of the two parts**"... if $k \geq 2$ how can he consider only two parts? Also in the same page he writes " let $P$ be the primitive action of $G$ on the blocks"... but there is no clear definition of $P$, is it a subgroup of $G$? Could you please help? Thanks.
Link: https://people.cs.uchicago.edu/~laci/students/codenotti.pdf
Consider Non-Trivial Cases
CC BY-SA 4.0
2021-08-15T19:22:50.000Z
@ConsiderNon-TrivialCases (1) The "two parts" refer to the two (given) parts $V_1, V_2$ of the vertices of the bipartite graph. (2) P will be a quotient of G, namely the image of G under $\varphi: G \to S_k$ determined by how $G$ it permutes the blocks. For example, consider $G=\langle (123), (14)(25)(36) \rangle$. A minimal system of (maximal) blocks is given by $B_1={123}$ $B_2={456}$. The action of G on these blocks is given by $(123) \mapsto (), (14)(25)(36) \mapsto (12)$, so here $P \cong C_2$.
Joshua Grochow
CC BY-SA 4.0
2021-08-17T18:42:03.140Z
Then I need help to grasp, how can we **first** apply the Equation (2.4) (which is $$\text{ISO}_{B}(G\sigma) = \text{ISO}_{B_1}( \text{ISO}_{B_2}(...\text{ISO}_{B_k}(G\sigma) ...))$$) 
on one of the parts of $V_1, V_2$, on which $G$-action is not transitive and **then** reduce to the case where G acts transitively on each part? (on page 34) **My understanding is**, if $B_i$ are $G$-invariant, then we can use the Equation (2.4), as written on the same page, just before the Equation (2.4), **how equation (2.4) reduces to the case where $G$ acts transitively on each part?**
Consider Non-Trivial Cases
CC BY-SA 4.0
2021-08-17T18:42:29.787Z
To be an element in  $\text{ISO}_{B_1 \cup B_2}$, first we find $\text{ISO}_{ B_1}$, and check which elements of $\text{ISO}_{ B_1}$ are also isomorphic for the sub-graph $B_1 \cup B_2$.
Consider Non-Trivial Cases
CC BY-SA 4.0
2021-08-17T18:49:27.877Z
We're a bit character-limited here, so I may be missing some nuance in what you're saying, but what you wrote looks right to me.
Joshua Grochow
CC BY-SA 4.0
2021-08-25T18:39:42.153Z
Okay.. he actually writes in correct order on page 35 ("In $K$ the blocks are invariant, hence we can apply Equation (2.4)").. I get the idea somewhat, but I am curious about what happens when $\text{ISO}(G;X,Y)=\emptyset$? Does it imply there is no isomorphism between $X$ and $Y$? But there might be another subgroup $H$ of  $\text{Sym}(V_1) \times \text{Sym}(V_2)$ other than $G$ for which $\text{ISO}(H;X,Y)$ is not empty, how can we be sure that searching $G$ is sufficient?
Consider Non-Trivial Cases
CC BY-SA 3.0
2015-12-12T04:26:26.927Z
2015-12-12T04:26:26.927Z
Joshua Grochow
<p>It really makes a difference what the input to the algorithm is: how do you specify a group?</p>

<p>If you want groups given by generators and relators, I would suggest <em>Combinatorial Group Theory</em>, by Magnus, Karrass, and Solitar (but algorithms there are sparse because too many of the important problems are undecidable).</p>

<p>If you want automatic groups (groups whose elements are strings of symbols and whose group operations are performed by finite automata, with applications in low-dimensional topology), I would suggest <em>Word Processing in Groups</em> by Epstein (not me!), Cannon, Holt, Levy, Paterson, and Thurston.</p>

<p>If you want permutation groups (the kind of group-theoretic algorithm that is most relevant e.g. for graph isomorphism) then Seress has a book <em>Permutation Group Algorithms</em> but I don't have a copy so I can't tell you whether it's any good.</p>

<p>There should be a fourth paragraph here about matrix group algorithms but I don't know of a book on that topic. There's a little coverage in Seress's book.</p>

CC BY-SA 3.0
2015-12-11T00:39:04.890Z
2015-12-12T06:21:04.503Z
2015-12-12T06:21:04.503Z
David Eppstein
<p>The most modern and comprehensive reference is probably "Handbook of Computational Group Theory" by Holt, Eick and O'Brien <a href="https://www.crcpress.com/Handbook-of-Computational-Group-Theory/Holt-Eick-OBrien/9781584883722">(link)</a></p>

<p>A classic reference is "Computation in Finitely Presented Groups" by Charles Simms.</p>

CC BY-SA 3.0
2015-12-11T19:59:08.293Z
2015-12-11T19:59:08.293Z
NietzscheanAI
<p>Not a book but maybe A. Hulpke's <a href="http://www.math.colostate.edu/~hulpke/CGT/cgtnotes.pdf">Notes on Computational Group Theory</a> are of interest? </p>

CC BY-SA 3.0
2015-12-11T20:49:50.417Z
2015-12-11T20:49:50.417Z
Martin Berger
<p>I cut my teeth on Combinatorial Algorithms Generation Enumeration Search, <a href="http://www.math.mtu.edu/~kreher/cages.html" rel="nofollow">http://www.math.mtu.edu/~kreher/cages.html</a>.</p>

<p>I would highly recommend it. You learn much faster coding group algorithms as by hand examples break down really quickly. Also grab a system like Sage or Magma to play with to use as a bench calculator.</p>

CC BY-SA 3.0
2015-12-15T18:46:02.213Z
Just a note that the chapter of this book on groups appears to be primarily about permutation groups.
David Eppstein
CC BY-SA 3.0
2015-12-15T18:11:44.507Z
2015-12-15T18:11:44.507Z
Chad Brewbaker
<p>If you're only concerned about finite permutation groups, I found the book <a href="http://www.springer.com/us/book/9783540549550" rel="nofollow">"Fundamental Algorithms for Permutation Groups"</a> by Gregory Butler very readable.  It's only for finite permutation groups but was one of the only books that gave pseudo code and algorithmic descriptions that I could understand (for Schreirer-Sims, strong generating sets, etc.).  The Seress book recommended by others is decent but for some reason he has an aversion to pseudo code so it was very difficult for me to understand.  Personally, I used the Butler book for a concrete understanding of the algorithms and the Seress book as aid in understanding proofs of correctness.</p>

<p>The Butler book is quite old by now but I still have yet to find a better introduction on finite permutation group algorithms.</p>

CC BY-SA 3.0
2015-12-16T23:10:32.043Z
2015-12-16T23:10:32.043Z
user834
<p>I am a math major interested on TCS. </p>

<p>I want to self-study the algorithms, and complexity of them for solving the group theoretical problems like find order of elements, coset enumeration, find generator, test if a given subset generates the group. </p>

<p>What book should I read?</p>

CC BY-SA 3.0
2015-12-10T03:37:33.270Z
Can you be more specific about what you mean by "the fundamental group theory problems"? Depending on your interests, different sources may be more or less appropriate...
Joshua Grochow
CC BY-SA 3.0
2015-12-14T17:05:32.637Z
Things like finding cosets, find generators, test if a subset of a group is a generator, find order of elements, find subgroups
ricardorr
CC BY-SA 3.0
2015-12-15T13:33:07.573Z
@ricardorr perhaps you could edit your question to make it more precise?  As Joshua says, there are several different classes of problems related to group theory.
András Salamon
<ds.algorithms><reference-request><gr.group-theory><books>
Book for self study of algorithms in group theory
ricardorr
# Book for self study of algorithms in group theory

(Asked by: username_0 on 2015-12-10)

I am a math major interested on TCS.

I want to self-study the algorithms, and complexity of them for solving the group theoretical problems like find order of elements, coset enumeration, find generator, test if a given subset generates the group.

What book should I read?

**Tags:** ds.algorithms, reference-request, gr.group-theory, books

> **Comments:**
> **username_1**: Can you be more specific about what you mean by "the fundamental group theory problems"? Depending on your interests, different sources may be more or less appropriate...  
> **username_0**: Things like finding cosets, find generators, test if a subset of a group is a generator, find order of elements, find subgroups  
> **username_2**: @username_0 perhaps you could edit your question to make it more precise?  As Joshua says, there are several different classes of problems related to group theory.  

---

## 6 answers

### Answer by username_1 on 2015-12-12. Score: 6 | Accepted answer

If you're interested in the group theory that's relevant for Graph Isomorphism, then in addition to Seress's book that username_4 mentioned, I would highly recommend

> Dixon and Mortimer's [Permutation Groups](http://www.ams.org/mathscinet-getitem?mr=1409812)

The above is a book on "just" group theory, but of the books on pure group theory, it is probably the most relevant to Graph Isomorphism.

A book that is more directly about algorithms for graph isomorphism, which puts group-theoretic algorithms at center stage, is:

> Christoph Hoffman. [Group-theoretic algorithms and graph isomorphism](http://dx.doi.org/10.1007/3-540-11493-9/). Springer Lecture Notes in Computer Science 136.

The latter (together with Paolo Codenotti's thesis) is currently one of the few widely accessible places where you can really find a complete account of some of the more group-theoretic algorithms for graph isomorphism.

> **Comments:**
> **username_3**: Hi! I can't ask questions that are not related to research, I am requesting you to respond to following questions related to Paolo's thesis:  Page 35 the author writes, "Let $B_1 \cdots B_k$ be a minimal system of imprimitivity (maximal blocks) of the $G$-action on **one of the two parts**"... if $k \geq 2$ how can he consider only two parts? Also in the same page he writes " let $P$ be the primitive action of $G$ on the blocks"... but there is no clear definition of $P$, is it a subgroup of $G$? Could you please help? Thanks. Link: https://people.cs.uchicago.edu/~laci/students/codenotti.pdf  
> **username_1**: @ConsiderNon-TrivialCases (1) The "two parts" refer to the two (given) parts $V_1, V_2$ of the vertices of the bipartite graph. (2) P will be a quotient of G, namely the image of G under $\varphi: G \to S_k$ determined by how $G$ it permutes the blocks. For example, consider $G=\langle (123), (14)(25)(36) \rangle$. A minimal system of (maximal) blocks is given by $B_1={123}$ $B_2={456}$. The action of G on these blocks is given by $(123) \mapsto (), (14)(25)(36) \mapsto (12)$, so here $P \cong C_2$.  
> **username_3**: Then I need help to grasp, how can we **first** apply the Equation (2.4) (which is $$\text{ISO}_{B}(G\sigma) = \text{ISO}_{B_1}( \text{ISO}_{B_2}(...\text{ISO}_{B_k}(G\sigma) ...))$$)  on one of the parts of $V_1, V_2$, on which $G$-action is not transitive and **then** reduce to the case where G acts transitively on each part? (on page 34) **My understanding is**, if $B_i$ are $G$-invariant, then we can use the Equation (2.4), as written on the same page, just before the Equation (2.4), **how equation (2.4) reduces to the case where $G$ acts transitively on each part?**  
> **username_3**: To be an element in  $\text{ISO}_{B_1 \cup B_2}$, first we find $\text{ISO}_{ B_1}$, and check which elements of $\text{ISO}_{ B_1}$ are also isomorphic for the sub-graph $B_1 \cup B_2$.  
> **username_1**: We're a bit character-limited here, so I may be missing some nuance in what you're saying, but what you wrote looks right to me.  
> **username_3**: Okay.. he actually writes in correct order on page 35 ("In $K$ the blocks are invariant, hence we can apply Equation (2.4)").. I get the idea somewhat, but I am curious about what happens when $\text{ISO}(G;X,Y)=\emptyset$? Does it imply there is no isomorphism between $X$ and $Y$? But there might be another subgroup $H$ of  $\text{Sym}(V_1) \times \text{Sym}(V_2)$ other than $G$ for which $\text{ISO}(H;X,Y)$ is not empty, how can we be sure that searching $G$ is sufficient?  

---

### Answer by username_4 on 2015-12-11. Score: 16

It really makes a difference what the input to the algorithm is: how do you specify a group?

If you want groups given by generators and relators, I would suggest *Combinatorial Group Theory*, by Magnus, Karrass, and Solitar (but algorithms there are sparse because too many of the important problems are undecidable).

If you want automatic groups (groups whose elements are strings of symbols and whose group operations are performed by finite automata, with applications in low-dimensional topology), I would suggest *Word Processing in Groups* by Epstein (not me!), Cannon, Holt, Levy, Paterson, and Thurston.

If you want permutation groups (the kind of group-theoretic algorithm that is most relevant e.g. for graph isomorphism) then Seress has a book *Permutation Group Algorithms* but I don't have a copy so I can't tell you whether it's any good.

There should be a fourth paragraph here about matrix group algorithms but I don't know of a book on that topic. There's a little coverage in Seress's book.


---

### Answer by username_5 on 2015-12-11. Score: 6

The most modern and comprehensive reference is probably "Handbook of Computational Group Theory" by Holt, Eick and O'Brien [(link)](https://www.crcpress.com/Handbook-of-Computational-Group-Theory/Holt-Eick-OBrien/9781584883722)

A classic reference is "Computation in Finitely Presented Groups" by Charles Simms.


---

### Answer by username_6 on 2015-12-11. Score: 3

Not a book but maybe A. Hulpke's [Notes on Computational Group Theory](http://www.math.colostate.edu/~hulpke/CGT/cgtnotes.pdf) are of interest?


---

### Answer by username_7 on 2015-12-15. Score: 2

I cut my teeth on Combinatorial Algorithms Generation Enumeration Search, <http://www.math.mtu.edu/~kreher/cages.html>.

I would highly recommend it. You learn much faster coding group algorithms as by hand examples break down really quickly. Also grab a system like Sage or Magma to play with to use as a bench calculator.

> **Comments:**
> **username_4**: Just a note that the chapter of this book on groups appears to be primarily about permutation groups.  

---

### Answer by username_8 on 2015-12-16. Score: 2

If you're only concerned about finite permutation groups, I found the book ["Fundamental Algorithms for Permutation Groups"](http://www.springer.com/us/book/9783540549550) by Gregory Butler very readable. It's only for finite permutation groups but was one of the only books that gave pseudo code and algorithmic descriptions that I could understand (for Schreirer-Sims, strong generating sets, etc.). The Seress book recommended by others is decent but for some reason he has an aversion to pseudo code so it was very difficult for me to understand. Personally, I used the Butler book for a concrete understanding of the algorithms and the Seress book as aid in understanding proofs of correctness.

The Butler book is quite old by now but I still have yet to find a better introduction on finite permutation group algorithms.


---

