Class got a bit more technical on this fine Friday morning! We began with Cayley’s Good Theorem and went into details about graph theory. Furthermore, we learned about fundamental domains as a building block to representing infinite groups through graphs.**Cayley’s Theorem****Theorem. **If is finitely generated then there exists a labelled oriented graph such that SYM.

This is massive because now if we have any finitely generated group, we can can represent it using our graph theory tool box. The term finitely generated when referring to groups group is tied to locally finite when we discuss graphs. Throughout the course we will deal with locally finite graphs so, in essence, this theorem presents us with the dream.

Before we go any further, I’d like to review some of the terminology. Namely SYM, a permutation of a graph which moves vertices to vertices and edges to edges in a one to one manner, while preserving the relationship between all aspects of a graph.

Before we prove Cayley’s theorem we need to develop a bit of machinery in order to make more sense of it all. We introduce a somewhat new idea for groups and generating sets.**Definition. **A group with a generating set and Cayley graph has

1.

2.

where has labels and orientation.

It is important to note that acts on G from the right, which will be standard notation throughout the course. This is most easily described through the figures drawn below of the representation of through different generating sets.

As it becomes clear, we can portray the same group in different ways, depending on the generating set that we choose.

We can also do the same thing for finite groups, as shown below for .

As an aside, I find these representations really cool! The structure reminded me a bit of Murray Gell-Mann’s Eightfold Way which is an organization scheme for hadrons which were essential to the formation of the quark model in particle physics.

Anyways, these new representations which we are able to assemble bring us to some big questions about infinity. First and foremost, when is a graph finite? The answer must be when the group is finite, stemming from the first part of the definition: .

Other questions asked were when we can say that is locally finite? When the generating set is finite! When is it finitely connected? Always! (since we can always act on an element of the generating set with the composition of its inverse and any other element). Finally, when does have a finite amount of relaters? When it is sufficient to have a finite amount in order to get to all desired points in the graph.

All of these questions are important to think about as we advance through the course.

Keeping the definitions and questions in mind we now can prove Cayley’s theorem!**Proof. **We prove the equivalence statement given in the theorem in both directions. We begin the proof by first showing that is a subgroup of SYM.

This direction requires us to show that acts on faithfully. We have already shown in the previous class that acts faithfully on so all we must do is verify that the action on edges, meaning that the action induces a map in . We define the action as , for , , and . Now let’s take and edge and let act on both vertices. We obtain , so the action preserves the edge. Moreover, the result has the same label and orientation as where the label and orientation are all determined by the generating set . This verifies that action which has faithfulness implied from the definition of SYM.

For the other direction we must show that SYM is a subgroup of . We go about this by induction, however, for time purposes we will show only the base case and leave the induction step for another time. We choose an arbitrary map SYM and consider for and . The hypothesis will be that our map acts exactly the same as on vertices and edges. As the base case consider , defined as the unconnected neighborhood. Since each vertex in has exactly one adjacent edge along with a given label and orientation pair. By definition of SYM is one to one

and respects the labeling and pairing. Thus we have that . It follows that and agree in .

We could now proceed to induct and conclude our proof. □

A few takeaways from the proof of this magnificent theorem are on the definitions behind Cayley graphs, which we will discuss later in the course. First of all, Cayley graphs are dependent on the generating set (up to something). This is rather vague — but as I said we will get to it later on! Second, groups act on Cayley graphs; however, if for two groups we have acting on for some generating set . This DOES NOT imply that . Finally, a more general statement about Cayley graphs is that we can read off relaters and equivalent words from that paths in a graph.

An addition piece of information that I have briefly read about is the question of transitivity of Cayley graphs. In fact, all Cayley graphs are transitive, however, not all transitive graphs are Cayley. Maybe we will learn more about this as the term goes on but it certainly seems to be a big deciding factor on whether a graph is Cayley or not.**Fundamental Domain**

Let’s begin, as always, with the definition.**Definition **Let act on . A \textit{fundamental domain} of the action is a minimal subset such that is closed and .

Once again, the figures below of several examples of groups explain the concept quite clearly. In essence, we are minimizing the necessary information needed in order to identify the group action. As groups get bigger (to infinity and beyond) we will want to express all the necessary information as concisely as possible as opposed to trying to draw infinity.

We cover two quick but important theorems which are fundamental (no pun intended) to our understanding.

**Theorem. **Let act on , a connected graph with fundamental domain . Then the set generates all of .

Once more the theorem is concerned with generating … I’m sensing a pattern here. The proof is brief and shown below.**Proof. **Let , , and a path from to . Notice, since is covered by the set . As in the theorem conditions, we assume that for some which is valid since is by definition closed.

Now observe that and . We can thus in duct on this patter to find that for all . It follows that and thus we can generate all of with elements in . □

The figure below represents how we can envision the set generating .

A final theorem for the day gives us an additional property of the fundamental domain and lets us conclude with good foresight into the future.

Let act on connected graph and let be a subgroup of . If the fundamental domain of the action of on is a union of copies of the action of on then . □**Theorem**

Here, represents the degree of over . This theorem gives us information about the groups internal subgroup structure and a very useful tool for representation of a group’s subgroups through graphs. In addition, it reminds of Galois theory ideas through computing the degree of the group over its subgroup.

The theorem uses the term copies which is closely related to the term coset which are able to form pictures or copies of parts of the group. For our purposes we will use the term \textit{transversal} of .**Definition. **A *transversal* of

is a set of such that and if then .

With this, we conclude this blog post! The proof of this final theorem will be covered in Monday’s lecture and the next major topic will be putting fundamental domains to use. Sure, we know what they are by definition, but how can we actually represent complex groups using them?

Sources:

- Chapter 1 from J. Meier Groups, Graphs, and Trees
- Generators & Cayley graphs from Cornell University — http://pi.math.cornell.edu/~mec/2008-2009/Victor/part3.htm

Great post, Osip! I would like to comment on the proof of the theorem that says intersections of copies of under group action generate the group. In the proof, you assume that there exists a sequence of having nontrivial intersections so that they also cover the path. The existence of this “overlapping” cover is indeed due to that a fundamental domain is closed. Note that since we require that the graph is connected. Topologically, this path-connectedness would imply connectedness. Then, if we cannot find such a cover for the path, a subgraph of would be disconnected, which contradicts our assumption.

Nice post, Osip! I especially like all of your images — they really help me understand what is going on.

Very engaging notes! I especially liked your illustration of the second to last theorem. I think that’s a proof that would make much less sense without the picture along side it.