Mathematics 357 – Combinatorics Discussion 5 – Group Actions April 25, 2005

Background

Last time, we introduced the abstract notion of a group (G, ∗) acting on a set X. Recall the idea: A group action is a mapping

\begin{matrix}G × X & → X \\ (g, x) & ↦ g · x \end{matrix}

with the properties that e · x = x for all x (the identity element in G acts as the identity mapping on X). Furthermore

g · (h · x) = (g ∗ h) · x

for all g, h ∈ G and x ∈ H (that is, the action is “compatible” with the group operation in G).

Today we will look at another property of group actions and work through a concrete example to develop some of the groundwork for a fundamental result called Burnside’s Theorem. This important result gives a formula for counting with symmetry.

Discussion Questions

A) Define a relation ∼_{G} on X by x ∼_{G} y if and only if there exists some g ∈ G such that g · x = y. Show that ∼_{G} gives an equivalence relation on X. (In combinatorial problems where some symmetries are present, enumeration problems often reduce to counting the number of equivalence classes for the ∼_{G} relation for G acting on some set X.)

Here’s the concrete problem we will consider today. Let T be an equilateral triangle in the plane (the vertices and edges form a geometric realization of the complete graph K_{3}). Let G = D_{3} be the group of rotation and reflection symmetries of T (G has order 6). Let X be the set of all colorings of the vertices of T using two colors, say red and blue.

B) We start by fixing the positions of the vertices in T, say by labeling them with the integers {1, 2, 3} in some particular way. What is |X|? List all the elements of X by drawing corresponding triangles, and indicating which vertices are colored which colors.

C) Now allow the dihedral group G to act on the triangle, and hence on the set of colorings (in the obvious way: just apply the rotations and reflections to the triangle, keeping track of which colors go where). Which colorings are equivalent under the action of G? How many different colorings are there up to this equivalence? (You should do this by “brute force”.)

D) In a group action like this, there are two important ways to keep track of what group elements fix which elements of the set.

1) For a given x ∈ X, we can look at all the elements of G that fix x. This is called

Stab(x) = {g ∈ G : g · x = x}

(“stab” for “stabilizer”). What are the elements of Stab(x) for each of the x ∈ X here? Do you notice something “algebraic” about each of these subsets of the group G = D_{3}?

2) On the other hand, given an element g ∈ G, we can look at the x ∈ X fixed by that

g. This set is called

Fix(g) = {x ∈ X : g · x = x}

What are the elements of Fix(g) for each of the g ∈ G.

E) One way to keep track of all the Stab(x) and Fix(g) is to make a big matrix with rows labeled by the elements of G, and columns labeled by the elements of X. Place a 1 in the row and column corresponding to a pair (g, x) if g · x = x, and 0 otherwise. Do that for the action here. How could you use this matrix to find |Fix(g)| or |Stab(x)| for some g or x? Explain.

Assignment

Writeups due in class Wednesday, April 27.