### In this blog, we aim to show 1) the existence of fundamental domains, 2) fundamental domains in Cayley graphs, and 3) a one-to-one correspondence between the transversal of subgroups and components of a fundamental domain of subgroups.

## 1. Existence of Fundamental Domains

Last week, we introduced the notion of a fundamental domain of an action . To remind ourselves, I repeat the definition here.

**Definition** 1.1 If a group acts on a connected graph , then we say a subset of , denoted as , is a fundamental domain of if the following three conditions are satisfied: 1) is closed (in the topological sense), 2) the union , and 3) is minimal meaning that no subsets of satisfy 1) and 2).

Given this definition, we saw last week that we could construct fundamental domains of on a hexagon. Indeed, fundamental domains are not unique, as we have seen from the very same example.

However, we would like to ask whether fundamental domains exist for any . At the first glance, it seems that we can naively start with some candidate such that condition 1) and 2) are satisfied. Then, we gradually shrink until the minimality condition 3) is satisfied. However, this may not work since there is no way to guarantee that the shrunk subset of is still closed.

Note that in the above example, if we start with the highlighted subset and performance the removing procedure, the minimal subset would not be closed. However, if one tries to take the closure, the minimality is not guaranteed again. There, we have to seek another way. Indeed, we state the existence of fundamental domains as a theorem. In its proof, we instead start with a minimal subgraph (warning: this is stronger than a subset!) that covers all vertices upon performing group actions, shown using Zorn’s Lemma. Then, we add some closed half-edges to cover all edges in a minimal fashion.

**Theorem 1.2 **If , where is connected, then there exists a fundamental domain

*Proof.* We start by defining a poset set with minimal structure. Pick any vertex Define In other words, we would like to contain a minimal amount of vertices concerning how the group action can move things around.

Next, with the sets defined, we specify our partial order as the usual set inclusion. To use Zorn’s Lemma, we check that is nonempty since the singleton . Then, we want to show that every chain has a maximal element. We assume that we have the following chain:

Then, we let ranging over all in the chain. We claim that

To prove the claim, we first quickly observe that . Then, we assume that . There must exist such that . Thus, by assumption, we conclude that

Therefore, we apply Zorn’s lemma to obtain a maximal element in with respect to inclusion, and we call it . We claim that ; in other words, upon group actions, covers all vertices of

Towards a contradiction, we let such that . Thus, since is connected, there exists a vertex path from to any vertex in . Without loss of generality, we take the shortest path . Let be the last vertex before arriving in . Then, we claim that is a larger set than . To prove the claim, it suffices to show that there is no nontrivial such that , which is an exact rephrase of . Therefore, we have the desired contradiction.

Next, we would like to extend our in a minimal fashion so that the entire graph can be covered. Here, edges are our only concerns since all vertices have been covered. Consider any edge that is not covered in . Observe that two endpoints of , which we call , should satisfy , where . Without loss of generality, we may append the half-edge containing to for any with endpoints and . Note that this process is equivariant up to the union of all , so we may as well consider the extension on , which we give the name . As a quick remark here, is not unique itself, which gives us the freedom to make suitable fundamental domains. (This would be a great opportunity to make some comments, like backtracking this process with the example of a hexagon.)

Finally, we check that is a fundamental domain of . First, it is closed since throughout the construction, we only used unions of countably many closed subsets (I suppose we need to assume the graph is locally finite here since locally finite graphs have countably many vertices and edges on my rough inspection. But this is definitely worth commenting on.)

Second, it covers all by construction. Third, it is minimal since adding any more points on the half edges would result in repetitions equivariantly. **▭**

## 2. Fundamental Domains of Cayley Graphs.

We can obtain many insights from the proof of Theorem 1.2. For example, we may understand the fundamental domains on different graphs. First, we introduce the following definition of vertex transitivity.

**Definition 2.1** For acting on , we say that the action is (vertex)-transitive if for any , there exists such that .

**Remark 2.2 **Groups acting on their Cayley graphs vertex-transitively. We say the underlying group is , then for any vertices , where , note that .

Then, we present a Corollary of Theorem 1.2.

**Corollary 2.3** If acts on a graph transitively, then a fundamental domain of this action is a star of half edges.

*Proof*. We start by observing that in the construction, by fixing a vertex , any other vertex is connected through through group action. Thus, in our notation, Then, by attaching half-edges, we obtain a star-like fundamental domain.

**Corollary 2.4 **For any group acting on its Cayley group on the left, there exists a fundamental domain that’s a star of half edges.

*Proof.* This result trivially follows from Remark 2.2 and Corollary 2.3.

We see this corollary in action through an example.

**Example 2.5** We consider the Cayley graph of Note that in the following picture, I draw the Cayley graph of generated by Here, I denote the black color as the edges corresponding to and the blue color as the edges corresponding to . Then, the two red highlighted portions denote two fundamental domains of acting on this Cayley graph (forgetting the labels and directed edges).

## 3. Fundamental domains of subgroups.

In this section, my discussion will give a different treatment than what was covered in the lecture. First, we introduce the orbit and stabilizer. And then, we realize the one-to-one correspondence between the transversal of subgroups and components of a fundamental domain of subgroups as a corollary of the Orbit-Stabilizer Theorem.

**Definition 3.1 **Let act on . For any , the stabilizer of is defined as

Stab

We say that an element is moved freely by if the stabilizer is trivial. If every element of is moved freely, then acts freely on .

**Remark 3.1′** In Diagram 1, if is in the intersections of multiple , then those are exactly the stabilizer of the vertex .

**Definition 3.2** Let act on . For any , the orbit of is defined as

Orb

**Remark 3.3** As a quick remark, in the proof of Theorem 1.2, when we define , we basically require that the subgraph does not contain any two vertices from the same orbit to obtain minimality.

**Theorem 3.4** Let act on and any , there is a one-to-one correspondence between the set Orb and left cosets of given by Stab

*Proof.* We observe that if and only if Thus, two elements in the orbit are the same if and only if their induced cosets are the same.

Coming back to the picture of fundamental domains, we wish to realize this nice result when the set is a graph .

**Theorem 3.5** Let act on with a fundamental domain . We assume that no group action fixes nontrivially. Then, if is a subgroup of and a fundamental domain of is a union of copies of (where can also be infinity), the index of in is

*Proof.* Since no group action fixes nontrivially, we deduce that there is some point in that is moved freely by . Therefore, we have a bijection between elements of and points in Orb. By assumption, we note that

where can also take on infinity.

Since is a fundamental domain for the action , we can deduce for one of the mentioned above. Using Theorem 3.4 to come back to the group side, we conclude that forms a transversal of in . Hence, we prove the theorem.

Shuhang! Great post!! I really liked how you laid out all the definitions and theorems we covered in class in a very logical and clear way. One thing I am still a bit confused about is the proof of Corollary 2.3, how do we know it is always a star of half edges? It seems very surprising to me that this is true but I think I’m just having trouble wrapping my head around it. I’ll work through it another time and do some examples and it might make more sense though.

Overall, amazing work!

In my understanding, its because that in the construction, we want a set of vertices that does not include any two verticies such that the group action on one will result in the other one. However, if a group acts transitively on a graph. Then by definition, you cannot include any other vertex but the one you started with. Then, you can add edges to complete the construction to see it is star-shaped.

Nice work! I really appreciated how you made a connection with the orbit-stabilizer relationship. I got a little lost in the proof of theorem 3.5 though. I think maybe the root of my confusion is that I’m not completely clear on what it means for no group action to fix the fundamental domain nontrivially. Could explain what you mean by that?

Sorry about the late reply. I meant that if , then has to be the identity element. Notice that I need this assumption to say that at least there is one point in that is movedly freely by . This point is needed in the proof to apply the orbit-stabilizer relation.

Shuhang. What a beautiful post. I’ve had little experience with Zorn’s lemma and was a little confused about the parts where you used it. Could you point me towards any resources or maybe just a few lines of intuition that helped you think about it?

Thank you! I state Zorn’s Lemma in the following language of postes.

Suppose we have a nonempty partially ordered set P. If every nonempty chain has an upper bound in P, then we have a maximal element on P.

I would encourage you to use this to prove some simple statements:

1. every vector space has a basis.

2. every nonempty ring with unity has a maximal ideal.

Indeed, I recall that Zorn’s lemma is equivalent to the Axiom of Choice, which may be an interesting exercise for folks. As for reference, I just learned it in algebra. Also, Wikipedia page might have decent enough information.

Nice post, Shuhang! I am still confused by the proof of Theorem 1.2. What exactly is the poset that you defined as ? How are we actually constructing it? I understand that . One of our conditions on is that . Does the here refer to an element of the larger set ?

Additionally, how are we showing that ? It is clear that it contains v, but how do we show the second condition? Any clarification would be appreciated!

Thank you. The poset consists of sets of vertices such that none will result in a distinct vertex upon a group action. Then, the partial relation here is just set inclusion. Therefore, it should be . Sorry if I had some typos.

As for the second question, we start with two arbitrary verticies . Then, by construction, they both live in a specific . Therefore, we can use our assumption on to conclude that the second condition is satisfied.

Awesome post! One thing your discussion of Fundamental Domains makes me think about is what an efficient Fundamental Domain generating algorithm might look like. You could certainly brute-force it by computing the behavior of every vertex and edge over every , and I’m not sure that in a general case you can be substantially faster than that. However, I’d be curious to know how computability changes based on the graph and the acting group.

That’s a great question, John. I don’t know the answer, but it reminds me of questions around automaticity of groups, which we will (hopefully) get to later in the term! If you’re interested, you could check out the book Word Processing in Groups from the library.