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

6 Mar

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 gives you 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 $\mathbb{Z}/ n\mathbb{Z}$, which is also written as $\mathbb{Z}_n$.  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 $\mathbb{Z}_{12}$.  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 $\pm 2, \pm 3$ instead of using 1, -1.  Different generating sets give you different pictures).  This picture is called the Cayley graph of the group 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.

### 13 Responses to “Cayley graphs, trees, Schreier’s theorem Part I (actually just groups)”

1. - April 4, 2013

[…] theory.  From my last math post you know what a graph is: a collection of vertices with some edges connecting them.  We’ll […]

2. - July 23, 2013

[…] we weren’t together.  I decided to talk about graph theory, which I’ve introduced in this previous post.  I basically gave this blog post as my presentation, only with a powerpoint and being dressed up […]

3. - November 16, 2013

[…] (which you probably haven’t), check out the “groups” section in my post about Cayley graphs, which was really just about groups.  I just need you to know what the group of integers is […]

4. - February 25, 2014

[…] you don’t know what a group is, check out my quick intro post for some examples.  Wikipedia also has a significantly more exhaustive […]

5. - March 2, 2015

[…] algebra and topology- “group theory” is the study of groups, which we’ve seen a few times before, and “geometric” means that we’ll be looking at shapes.  Geometric […]

6. - April 26, 2015

[…] Last summer, I participated in an awesome research program which ended up with a good handful of original research projects all having to do with random groups.  Random group theory is rather modern- the first definition of a random group came about in the 1980s (just like me!)  It’s a very rich field with lots and lots of open problems, since you can dive into most properties of groups and ask if they apply to random groups. [Here’s the post defining groups if you forgot.] […]

7. - May 13, 2015

[…] you remember or know what a group is.  A pree is something on the way to being a group, but not quite: it’s a set with partial […]

8. - May 29, 2015

[…] talked before about what a group is– a set of elements with some operation that takes two elements to another one (like addition […]

9. - June 25, 2015

[…] that a group is a collection of elements paired with some kind of operation between them (the integers with […]

10. - July 30, 2015

[…] be talking about a property of groups, so brush up from a previous blog post or wikipedia.  First we need to define a  (total) ordering on a group: a binary […]

11. - September 24, 2015

[…] amount + an additive error term).  We say a group G is quasi-isometric to a space X if its Cayley graph is quasi-isometric to X.  Remember, a Cayley graph is a picture you can draw from a group if you […]

12. - November 14, 2015

[…] I say “group” when I’m obviously referring to a space, and then I mean the Cayley graph of that group (which changes depending on generating set, but if it’s a finite generating set […]

13. - November 8, 2016

[…] is the image of another under one of the reflections, you get something that looks a lot like the Cayley graph of the reflection triangle group.  The only difference is that each edge needs to be two edges […]