14
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • 4
    $\begingroup$ 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... $\endgroup$
    – Joshua Grochow
    Commented Dec 10, 2015 at 3:37
  • $\begingroup$ Things like finding cosets, find generators, test if a subset of a group is a generator, find order of elements, find subgroups $\endgroup$
    – ricardorr
    Commented Dec 14, 2015 at 17:05
  • $\begingroup$ @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. $\endgroup$
    – András Salamon
    Commented Dec 15, 2015 at 13:33

6 Answers 6

Reset to default
6
$\begingroup$

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

Dixon and Mortimer's Permutation Groups

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. 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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ 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: people.cs.uchicago.edu/~laci/students/codenotti.pdf $\endgroup$
    – Consider Non-Trivial Cases
    Commented Aug 15, 2021 at 15:41
  • 1
    $\begingroup$ @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$. $\endgroup$
    – Joshua Grochow
    Commented Aug 15, 2021 at 19:22
  • $\begingroup$ 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? $\endgroup$
    – Consider Non-Trivial Cases
    Commented Aug 17, 2021 at 18:42
  • $\begingroup$ 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$. $\endgroup$
    – Consider Non-Trivial Cases
    Commented Aug 17, 2021 at 18:42
  • $\begingroup$ 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. $\endgroup$
    – Joshua Grochow
    Commented Aug 17, 2021 at 18:49
16
$\begingroup$

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.

Improve this answer
$\endgroup$
6
$\begingroup$

The most modern and comprehensive reference is probably "Handbook of Computational Group Theory" by Holt, Eick and O'Brien (link)

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

Improve this answer
$\endgroup$
0
3
$\begingroup$

Not a book but maybe A. Hulpke's Notes on Computational Group Theory are of interest?

Improve this answer
$\endgroup$
2
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Just a note that the chapter of this book on groups appears to be primarily about permutation groups. $\endgroup$
    – David Eppstein
    Commented Dec 15, 2015 at 18:46
2
$\begingroup$

If you're only concerned about finite permutation groups, I found the book "Fundamental Algorithms for Permutation Groups" 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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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