Tag Archives: group theory

Solving Permutation-Based Puzzles

Introduction In the previous article, we described the Schreier-Sims algorithm. Given a small subset which generates the permutation group G, the algorithm constructs a sequence such that for: we have a small generating set for each Specifically, via the Sims … Continue reading

Posted in Uncategorized | Tagged , , , , , | Leave a comment

Schreier-Sims Algorithm

Introduction Throughout this article, we let G be a subgroup of generated by a subset  We wish to consider the following questions. Given A, how do we compute the order of G? How do we determine if an element lies in G? Assuming , how … Continue reading

Posted in Uncategorized | Tagged , , , , , , | Leave a comment

Burnside’s Lemma and Polya Enumeration Theorem (2)

[ Acknowledgement: all the tedious algebraic expansions in this article were performed by wolframalpha. ] Counting Graphs One of the most surprising applications of Burnside’s lemma and Polya enumeration theorem is in counting the number of graphs up to isomorphism. … Continue reading

Posted in Notes | Tagged , , , , , , , , | Leave a comment

Burnside’s Lemma and Polya Enumeration Theorem (1)

[ Note: this article assumes you know some rudimentary theory of group actions. ] Let’s consider the following combinatorial problem. Problem. ABC is a given equilateral triangle. We wish to colour each of the three vertices A, B and C by … Continue reading

Posted in Notes | Tagged , , , , , , , | Leave a comment

Introduction to Ring Theory (6)

Let’s keep stock of what we’ve covered so far for ring theory, and compare it to the case of groups. There are loads of parallels between the two cases. G is a group R is a ring. Abelian groups. Commutative … Continue reading

Posted in Notes | Tagged , , , , | Leave a comment

Intermediate Group Theory (5)

Free Groups To motivate the concept of free groups, let’s consider some typical group G and elements a, b of G. Recall that , the subgroup generated by {a, b}, is defined to be the intersection of all subgroups of G containing a and b. Immediately, we see … Continue reading

Posted in Notes | Tagged , , , , | Leave a comment

Intermediate Group Theory (4)

Applications We’ll use the results that we obtained in the previous two posts to obtain some very nice results about finite groups. Example 1. A finite group G of order p2 is isomorphic to either Z/p2 or (Z/p) × (Z/p). In particular, it … Continue reading

Posted in Notes | Tagged , , , , , | Leave a comment