12
$\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?

$\endgroup$
  • 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 Dec 10 '15 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 Dec 14 '15 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 Dec 15 '15 at 13:33
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.

$\endgroup$
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.

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

$\endgroup$
4
$\begingroup$

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

$\endgroup$
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.

$\endgroup$
1
$\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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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