Friday of Week 1: Cayley’s “Better” Theorem and Fundamental Domains

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 $G$ is finitely generated then there exists a labelled oriented graph $\Gamma$ such that SYM $^+(\Gamma)\cong G$ .

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 $G$ with a generating set $S$ and Cayley graph $\Gamma_{G,S}$ has
1. $ V(\Gamma)=G, $

2. $E(\Gamma)={(g,gs)| s\in S},$
where $(g,gs)$ has labels and orientation.

It is important to note that $s$ 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 $\mathbb{Z}$ 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 $\mathbb{Z}/6\mathbb{Z}$ .

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 $\Gamma_{G,S}$ finite? The answer must be when the group is finite, stemming from the first part of the definition: $v(\Gamma)=G$ .
Other questions asked were when we can say that $\Gamma_{G,S}$ 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 $\Gamma_{G,S}$ 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 $G$ is a subgroup of SYM $^+(\Gamma)$ .
$(\implies)$ This direction requires us to show that $G$ acts on $\Gamma_{G,S}$ faithfully. We have already shown in the previous class that $G$ acts faithfully on $V(\Gamma)$ so all we must do is verify that the action on edges, meaning that the action induces a map in $E$ . We define the action as $g\cdot v_x=v_{gx}$ , for $g\in G$ , $x\in S$ , and $v_x,v_{gx}\in V(\Gamma_{G,S})$ . Now let’s take and edge $(v_x,v_s)$ and let $g$ act on both vertices. We obtain $g\cdot(v_x,v_s)=(v_{gx},v_{gs})\in E$ , so the action preserves the edge. Moreover, the result has the same label and orientation as $(v_x,v_{xs})$ where the label and orientation are all determined by the generating set $S$ . This verifies that action which has faithfulness implied from the definition of SYM $^+(\Gamma)$ .
$(\Longleftarrow)$ For the other direction we must show that SYM $^+(\Gamma)$ is a subgroup of $G$ . 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 $\phi\in$ SYM $^+(\Gamma)$ and consider $\phi(v_e)=v_g$ for $v_e,v_g\in V(\Gamma_{G,S})$ and $e,g\in G$ . The hypothesis will be that our map $\phi$ acts exactly the same as $g\in G$ on vertices and edges. As the base case consider $N(v_e)$ , defined as the unconnected neighborhood. Since each vertex in $V(\Gamma_{G,S})$ has exactly one adjacent edge along with a given label and orientation pair. By definition of SYM $^+(\Gamma)$ $\phi$ is one to one
and respects the labeling and pairing. Thus we have that $\phi(v_e,v_{es})=(v_g,v_{gs})$ . It follows that $\phi$ and $g$ agree in $N_1(v_e)$ .
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 $G,H$ we have $G$ acting on $\Gamma_{H,S}$ for some generating set $S$ . This DOES NOT imply that $G\cong H$ . 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 $G$ act on $\Gamma$ . A \textit{fundamental domain} of the action is a minimal subset $\mathcal{F}\subseteq \Gamma$ such that $\mathcal{F}$ is closed and $\bigcup g\cdot \mathcal{F}=\Gamma$ .

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 $G$ act on $\Gamma$ , a connected graph with fundamental domain $\mathcal{F}$ . Then the set $S={g\in G|\mathcal{F}\bigcap g\mathcal{F}\neq \emptyset}$ generates all of $G$ .

Once more the theorem is concerned with generating $G$ … I’m sensing a pattern here. The proof is brief and shown below.

Proof. Let $g\in G$ , $v\in V(\Gamma)$ , and $\gamma$ a path from $v$ to $g\circ v$ . Notice, since $\bigcup g\cdot \mathcal{F}=\Gamma$ $\gamma$ is covered by the set ${g_i\mathcal{F}}$ . As in the theorem conditions, we assume that $g_1\mathcal{F} \cap g_{i+1} \mathcal{F}\neq \emptyset$ for some $i$ which is valid since $\mathcal{F}$ is by definition closed.
Now observe that $g_1\in S$ and $g_2g_1^{-1}\in S$ . We can thus in duct on this patter to find that $g_{i+1}g_i^{-1}\in S$ for all $i$ . It follows that $g=g_n=(g_n g_{n-1}^{-1})(g_{n-1} g_{n-2}^{-1})...(g_2 g_{1}^{-1})g_1$ and thus we can generate all of $G$ with elements in $S$ . □

The figure below represents how we can envision the set $S$ generating $G$ .
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 $G$ act on connected graph $\Gamma$ and let $H$ be a subgroup of $G$ . If the fundamental domain $\mathcal{F}$ of the action of $G$ on $\Gamma$ is a union of $n$ copies of the action of $H$ on $G$ then $[G:H]=n$ . □
Theorem
Here, $[G:H]$ represents the degree of $G$ over $H$ . 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 $H\subseteq G$ .

Definition. A transversal of $H\subseteq G$
$begin{equation} {e,g_1,g_2,... g_n}$
is a set of $g_i\in G$ such that $\bigcup g_i H = G$ and if $g_i H \bigcap g_j H\neq\emptyset$ then $i=j$ .

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

3 Responses to Friday of Week 1: Cayley’s “Better” Theorem and Fundamental Domains

Shuhang Xue says:

September 20, 2022 at 8:51 pm

Great post, Osip! I would like to comment on the proof of the theorem that says intersections of copies of $\mathcal{F}$ under group action generate the group. In the proof, you assume that there exists a sequence of $\{g_i\cdot \mathcal{F}\}$ 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 $\Gamma$ would be disconnected, which contradicts our assumption.

Michaela Polley says:

September 21, 2022 at 5:38 pm

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

Horace Fusco says:

September 24, 2022 at 6:29 pm

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.

Friday of Week 1: Cayley’s “Better” Theorem and Fundamental Domains

3 Responses to Friday of Week 1: Cayley’s “Better” Theorem and Fundamental Domains

Leave a Reply to Michaela Polley Cancel reply

Recent Posts

Recent Comments