\magnification=\magstep1
\centerline{Mathematics 357 -- Combinatorics}
\centerline{Discussion 5 -- Group Actions}
\centerline{April 25, 2005}
\bigskip
\noindent
{\it Background}
\bigskip
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
$$\eqalign{ G \times X &\to X\cr
               (g,x) &\mapsto g\cdot x\cr}$$
with the properties that $e\cdot x = x$ for all $x$ (the identity
element in $G$ acts as the identity mapping on $X$).  Furthermore
$$g\cdot (h \cdot x) = (g * h)\cdot x$$
for all $g,h \in G$ and $x \in 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 {\it Burnside's
Theorem}.  This important result gives a formula for counting 
with symmetry.

\bigskip
\noindent
{\it Discussion Questions}
\bigskip
\noindent
A)  Define a relation $\sim_G$ on $X$ by $x \sim_G y$ 
if and only if there exists some $g\in G$ such that $g\cdot x = y$.
Show that $\sim_G$ gives an {\it equivalence relation} on $X$.  
(In combinatorial
problems where some symmetries are present, enumeration problems
often reduce to {\it counting the number of equivalence classes}
for the $\sim_G$ relation for $G$ acting on some set $X$.)

\bigskip
\noindent
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.
\bigskip
\noindent
B)  We start by {\it 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.
\bigskip
\noindent
C)  Now allow the dihedral group $G$ to act on the triangle, and 
{\it 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''.)
\bigskip
\noindent
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.
\medskip
\item{1)}  For a given $x \in X$, we can look at all the 
elements of $G$ that fix $x$.  This is called
$${\rm Stab}(x) = \{ g \in G : g\cdot x = x\}$$
(``stab'' for ``stabilizer'').
What are the elements of ${\rm Stab}(x)$ for each of the $x\in X$
here?  Do you notice something ``algebraic'' about each of these subsets of
the group $G = D_3$?
\item{2)}  On the other hand, given an element $g \in G$, we can
look at the $x \in X$ fixed by that $g$.  This set is called
$${\rm Fix}(g) = \{x \in X : g\cdot x = x\}$$
What are the elements of ${\rm Fix}(g)$ for each of the $g\in G$.
\bigskip
\noindent
E)  One way to keep track of all the ${\rm Stab}(x)$ and ${\rm 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\cdot x = x$,
and $0$ otherwise.  Do that for the action here.  How could 
you use this matrix to find $|{\rm Fix}(g)|$ or $|{\rm Stab}(x)|$
for some $g$ or $x$?  Explain.
\bigskip
\noindent
{\it Assignment}
\bigskip
Writeups due in class Wednesday, April 27.
\bye

here?