Cayley graphs, trees, Schreier’s theorem Part I (actually just groups)

So that’s a big agenda, but hey, dream big, right?  I’m giving a talk in our geometry, topology, and dynamics graduate seminar tomorrow on Schreier’s theorem, so I thought I’d try to write a blog post or three about it.   And then maybe blog about some cranberry cookies I made tonight after preparing my talk.

First, we’ve got to talk about the fundamental object of abstract algebra, pretty much the first thing you learn about as a math major: groups.  Abstractly, a group is a collection of objects that have some type of operation between them, where the operation satisfies a good number of properties: doing the operation to any two objects (or elements) results in another element in the group (this is called closure); there’s an identity element so that if you operate it with any other element, you get that other element back; the operation should be associative which means you can move parentheses around; and each element should have an inverse that takes you back to the identity.  Concretely, here are some groups:

• The integers, with addition as your group operation.  Adding any two integers gives you an integer (closure); adding 0 to any number x gives you x back, so 0 is the identity; addition is associative; and x+ (-x) = 0, so every element has an inverse.
• Symmetries of a square.  This means all the ways you can turn, flip, and change a square.  The group operation is doing one symmetry, and then another (like flipping, and then turning).  What’s interesting about this group is that it can be generated by just two different symmetries: rotating to the right by 90 degrees, and flipping vertically.   You can convince yourself of this by taking a piece of paper and numbering the corners 1, 2, 3, 4 and figuring out how many ways there are total to get the square back again.  Or you can try drawing a non-symmetric smiley face in Paint!
  

  Symmetries of a square. Red guy is totally random

• Another is , which is also written as .  This can be read as the integers modulo n, which means every time you hit n, you jump back to 0.  It’s exactly how we count the hours up to 11, and then 12, and then we’re back at 1 again.  So our way of telling time .  If I tell you that it’s 10 o’clock now, and ask you what time it’ll be in 70 hours, and you answer 8 o’clock, you just did modular arithmetic.  So you figured out that the closest multiple of 12 to 70 was 60, and then you knew we had to add 10 to our time, but since you’re not in not-the-US you knew the answer couldn’t be 20 o’clock, and you got 8 o’clock.  Good for you, you just did some group theory!
  

  Flava Flav gets group theory

Okay, but I’m interested in geometric objects and pictures we can draw besides these little smiley face squares.  So how can I encode the data in our examples (the integers, the integers mod n, and the reflections of a square) into a geometric object?  I’ll use a diagram that computer scientists use a lot, called a graph.

Building our graph is like when we built our curve complex last time we did math.  We’ve got vertices, each of which represents a group element.  To connect two group elements with edges, we’ve got to figure out a generating set for our group.  This is a subset of the group elements, where if you operate with them over and over again, you end up with all of the group.  For instance, I can use {1,-1} as my generating set for the integers: I can add 1 to itself n times to get any positive integer n, and similarly for the negative integers.  And we used the rotation r and the vertical flip s in our smiley face picture above to generate the symmetries of a square.

So to connect two vertices, we draw an edge if we can operate by one of our generating set to get from one vertex to another.  So the picture of the integers looks like:

Here, we use little arrows for the vertices, and lines for the edges.  I very obviously didn’t make this picture.

This picture is from wikipedia!  It’s the picture for those rotations of the square.  Wikipedia used a letter ‘F’ instead of a smiley face.

So we can make these pictures for any group given some generating set (aside: generating sets aren’t unique.  For instance, you can generate the integers with instead of using 1, -1.  Different generating sets give you different pictures).  This picture is called the Cayley graph of the group G with respect to the generating set S. 

A graph without any loops/cycles/ways to get from one vertex back to itself is called a tree.  Boom, we’ve got two vocabulary words from the title down!  In Part II, I’ll actually explain what Schreier’s theorem is and maybe give some idea as to its proof.

Tags: Cayley graph, graph, group theory