First Wednesday: Groups, Graphs, and Symmetries

Posted on September 16, 2022 by John Eichelberger

Wednesday’s class was a review of groups, a “whirlwind-review” of the basics of graphs and trees, and a look at actions on symmetry groups of geometric object.

Groups, Reviewed

To begin with, we reviewed group presentations, of form $G = \langle S \ | \ R \rangle$ . For instance, the integers over addition can be conceived of as

$\mathbb{Z} = \langle t \ | \ \rangle = \{\ldots, t^{-2}, t^{-1}, e, t, t^{2}, \ldots\}$

In particular, we note that exponentiation works as expected, where exponentiation represents addition:

$t^m t^n = t^{m+n}$

What is “the” representation of \mathbb{Z} \times \mathbb{Z}? In short, it depends; there are infinitely many valid representations. For instance,

$\mathbb{Z} \times \mathbb{Z} &= \langle t, s \ | \ st = ts \rangle$
$\langle (1, 1), (0, 1) \ | \ \text{some relator} \rangle$
$\langle st, t \ | \ \text{some relator} \rangle$
$\langle st, t \ | \ \text{some relator} \rangle$
$\langle s, t, u \ | \ u = s^2, st = s \rangle$

However, while these are all representations of the same group, we cannot just “simplify” one into another. It’s true that generators are analogous to a basis in linear algebra, in the sense that groups are constructed by combinations of generators just as a vector space is constructed from its constituent vectors. But the analogy is strained when it comes to a “minimal basis”. Consider the following example:

$\mathbb{Z}/30\mathbb{Z} &= \langle 2, 3, 5 \ | \ \text{some relators}\rangle \cong \langle 1 \ | \ 1^{30} \rangle$

These both represent the same group; the first has three generators, and the second only has one. Yet in both cases the removal of any generator means we no longer have the same group.

This warm-up leads us to several key, enduring questions across geometric group theory:

For a group $G$ , is $G$ finitely presented? Is it finitely generated?
When is a presentation trivial? Given a presentation, when does it represent $\{e\}$ ?
Given a word $w \in S$ , does $w = e$ ?

Group Actions

Definition. A group $G$ acts on a set $X$ where for every $g \in G$ ,

$g: X \to X, \text{ and } g: x \mapsto g \cdot x$

with the following properties satisfied:

$gh \cdot x = g \cdot (h \cdot x)$
$e \cdot x = x$

We want to think about this definition in a deeper way, thinking about symmetry. So for an object $X$ , consider Sym $X$ , the group of symmetries on $X$ . (This is often referred to as Aut $X$ , the automorphisms on $X$ .) We can think of $G$ acting on $X$ as a homomorphism

$\varphi: G \to \text{Sym}X$

In other words, we want to assign the behaviors of elements of $G$ to the behaviors the groups that arise in $X$ .

We have a faithful group action if $\varphi$ is injective. Equivalently, $G$ acts faithfully if $g \neq e$ implies that there is some $x \in X$ such that $g \cdot x \neq x$ , or in other words, that every non-identity element of $g$ does something to some element of $X$ under the action. For an example of a faithful action, consider actions on a square, letting $G = \langle t \ | \ t^4\rangle$ . We define the action as $\varphi: t \mapsto r_{90}$ . This action is faithful, because every non-identity $g$ will permute the corners of the square.

For an example of an action that is not faithful, we’ll consider the trivial case: for any $X$ and any $G$ acting on $X$ , we can define the action by $g \cdot x = x$ . In other words, every configuration of $X$ maps to itself under every action of $G$ .

Theorem. Every group $G$ can be faithfully represented by a group action on the symmetries of an object $X$ .

Proof. Let the object $X$ be given by the set of elements of $G$ . We’ll define our action $g \cdot x$ as the multiplication operator of $G$ , which is to say $gx$ . This action will be associative because $g, x \in G$ , and because $G$ is (also) a group, elements under its operator associate; it likewise follows that our action will have an identity, since $G$ is a group. Finally, consider some $g \neq e \in G$ , and let $x = g^{-1}$ . We have that $g \cdot x = e \neq x$ , so for every $g \in G$ there is some $x \in X$ such that $g \cdot x \neq x$ , as desired.

The following corollary serves as a generalization of Cayley’s Theorem from Abstract I, that every finite group is a subgroup of a symmetric group.

Corollary. $G \subseteq \text{Sym}X$ for some $X$ .

Proof. It follows from the above theorem that $\varphi: G \to \text{Sym}X$ is injective. Thus

$G \cong \varphi(G)/\text{ker}\varphi \cong \varphi(G) \subseteq \text{Sym}X$

A Whirlwind of Graph Theory

The following are some foundational definitions for graph theory.

Definition. A graph $\Gamma$ is a set containing

$V(\Gamma)$ , a set of vertices,

$E(\Gamma)$ , a multiset of edges

Below is an example graph $\Gamma$ .

Definition. A path is a collection of edges and vertices that begins and ends with a vertex, with each edge connected to the previous vertex.

Note. The length of a path is given by the number of edges.

Definition. A path with the same initial and final vertex is a cycle.

Definition. A path is considered reduced if it contains no backtracks.

Definition. A graph is considered connected if there exists a path between any pair of vertices.

Definition. A graph is considered finite if $|V(\Gamma)|$ and $|E(\Gamma)|$ are finite.

Definition. A graph is considered locally finite if deg $(v)$ is finite for all $v \in V(\Gamma)$ .

Definition. A tree is a connected graph with no cycles.

Note. We denote $T_n$ as the regular tree, given by a tree where every vertex connects to $n$ edges. Similarly, $T_{n, m}$ refers to a tree in which every vertex has either $n$ or $m$ vertices.

Theorem. The following are equivalent:

$T$ is a tree.
There exists a unique reduced path for all $v, w \in V(T)$ .
For all $e \in E(T)$ , $T - e$ is disconnected.

These can be shown to follow by contradiction.

Symmetries on Graphs

With this setup, we can consider actions on graphs! Similar to rigid symmetries, we require that a symmetry $\varphi \in \text{Sym}(\Gamma)$ must be a bijective map of edges and vertices, and that $\varphi$ must preserve some sense of structure in the graph, what MurphyKate calls “preserving gluing.”

To get a sense for what this means, consider two graphs. $K_4$ is the graph of four points, each connected to every other point by an edge.

By numbering the points, we see that we can swap any pair of points as we please and preserve the shape of the graph. Therefore the group of symmetries on $K_4$ is isomorphic to $S_4$ , the symmetries on four elements.

On the other hand, consider the graph $\Gamma$ .

If we swapped 1 and 4, we would lose the property of “gluedness”. Similarly, we aren’t allowed to swap 2 and 4. Therefore we have that Sym $\Gamma \subset S_4$ . It turns out that Sym $\Gamma$ , with its four points and four edges, is isomorphic to $D_8$ , the rigid symmetries of a square.

But we can kick it up a notch with multiedges. The colors in $\Gamma'$ below mark where each part of its symmetry group come fromm and are not considered decorations:

But we can kick it up another notch with digraphs!

Definition. A directed graph (aka digraph) is a graph where every edge has an orientation toward a vertex. For instance:

That example has only one symmetry, formed by swapping the left and right multiedges. But we can kick it up again with colors! We can color every edge:

This example has only the trivial symmetry. So when considering a graph, we can consider separately Sym $(\Gamma)$ , as previously established, and Sym $^+(\Gamma)$ , the symmetry group that preserves orientation and color.

Theorem. For any graph $\Gamma$ , Sym $^+(\Gamma) \subseteq \text{Sym}(\Gamma)$ .

Proof. Left as an exercise. <3

And weighing in at five pages in Google docs, that wraps up my notes. Friday we’ll talk about Cayley graphs, and if I’m reading the textbook chapter headers correctly, the topic of group actions on the symmetry groups of graphs will last us most of the term.

This entry was posted in Uncategorized. Bookmark the permalink.

12 Responses to First Wednesday: Groups, Graphs, and Symmetries

Sam Hiken says:

September 16, 2022 at 3:38 pm

Yay graph theory! 🙂

Great write-up John! You give a very nice review of group actions and introduction to graphs. Interestingly, some of the terminology we used on Wednesday for graph-related concepts differs from what I’ve seen in combinatorics / theoretical CS contexts. For instance, most definitions of “path” I’ve seen have specified that a path does not permit repeated vertices (while a path with repeated vertices and edges might be considered a “walk”). It’s interesting that GGT would have a different approach to defining this term. I wonder if there’s some algebraic reason it’s more convenient to allow for repeated vertices and edges.

Reply
- MurphyKate says:
  
  September 19, 2022 at 3:22 pm
  
  Great question! My quick answer is that it depends on the specifics of your definition. We’re trying to define it combinatorially here, so we’ll allow “repeated edges” as long as you start going one direction along the edge and then go the other direction. We don’t allow repeated vertices (note that the definition requires that we alternative vertex and edges). It is OK to cover some vertex twice – if this is disallowed in CS it’s probably because it’s inefficient! (Though you might want to chat with your CS prof about this).
  
  Reply
  - Sam Hiken says:
    
    September 27, 2022 at 12:51 am
    
    This is a really interesting explanation. It’s true that algorithmists and complexity theorists are usually interested in problems regarding paths without repeated vertices, as they arise naturally in optimization contexts. Several classic NP-hard problems are also related to paths without repeated vertices (see: the Hamiltonian Path problem), while analogous problems on paths with repeated vertices are easy to compute (see: Eulerian trails). In a vague sense, problems related to paths require more knowledge about the structure of the underlying graph when they require that the path contain each vertex at most once.
    
    Additionally, statements that assume the existence of a path between two vertices can be made with the more restrictive definition (example: “a graph is connected if there exists a path between any pair of vertices”). Moreover, graph theorists may want to study paths without repeated vertices because such a path can itself be considered a subgraph of the larger graph. This allows one to define some interesting notions (see: pathwidth) that conceive of paths as a class of graphs, rather than a sequence of vertices and edges.
    
    Reply
Akash Ganguly says:

September 17, 2022 at 10:54 pm

Nice blog post! I realized as I read it that I’ve been visualizing group actions in terms of graph theory almost subconsciously. For example, when I think about the symmetries of a square, I’ve been seeing the square as a planar graph, and separating all of the edges and vertices and rearranging them.

My first introduction to group actions was in the context of . The ‘boolean algebra of rank 3’ was defined as the set B3 = {{123},{12},{13},{23},{1},{2},{3},{}}. (the last one being the empty set). It’s the combinations of 3 objects. I then looked for orbits of the action of the transposition (12). The action would send {1} to {2}, and {2} back to {1} forming one orbit. {13} and {23} are a similar case, and we consider {12} and {21} to be the same in this context. Finally, we end up with the orbits [{123}],[{12}],[{13},{23}],[{3}],[{1},{2}],[{}]. This then led to a ‘quotient poset’ where elements of the same orbit are considered the same element. These can be represented more visually through a Hasse diagram, but I can’t figure out how to add images to these comments so please shoot me a message if you’d like to see them!

Reply
- John Eichelberger says:
  
  September 19, 2022 at 3:45 pm
  
  I agree, the idea of orbitals as an actual *path* was how I originally conceptualized the idea of being able to have a subset of states you can reach from a given starting point in a group. I have very little background in graph theory, and it’s been satisfying to see that this vague understanding of structure can be modeled precisely.
  
  And yes, Hasse diagrams are awesome!
  
  Reply
Shuhang Xue says:

September 18, 2022 at 5:37 pm

I give a comment on the usage of Symmetric Group in the post and also in the textbook. The common symmetric groups $S_n$ we are in love with are a special case of a general symmetric structure. The notation of my discussion is based on our textbook.

Indeed, we can consider an arbitrary mathematical object $X$ . It can be a regular n-gon, a finite set, or even a vector space. Then, we can define the SYM(X) as the set of all bijections from $X$ to $X$ that preserves the underlying structure of the object. Under such a general context, we note that SYM(n-gon) is the dihedral group $D_2n$ ; SYM( $\{1,2,...,n\}$ ) is $S_n$ ; and SYM( $V$ ), where $V$ is a vector space, is the group of all linear operators.

With this machinery, we can make sense of John’s discussion of Cayley’s Theorem. Indeed, we view the symmetric group of a group $G$ as a subgroup of the symmetric group of the underlying set structure, namely $S_n$ , where $n=|G|$ . Thus, by the transitivity of subgroups, any group is realized as a subgroup of symmetric groups through an action induced by the multiplication of the group. This is a beautiful theorem since it reassures our intuition about groups, a well-orchestrated set structure –– groups are symmetric objects that are always realizable through permutations.

Shuhang Xue

Reply
Shuhang Xue says:

September 18, 2022 at 6:32 pm

I also want to discuss the graphs of our interest in the textbook. Indeed, we view graphs topologically. In concrete terms, we see graphs as CW-complexes with only zero and one cells, which is standardly denoted as $e^k_\alpha$ each homeomorphic to $D_k$ the $k$ -dimensional disk, where $k$ denotes the dimension and $\alpha$ denotes the index of cells. This construction builds topological spaces iteratively at each level $X_k$ by specifying gluing maps $\delta e^k_\alpha \to X_{k-1}$ . We call each $X_k$ as the $k-$ skeleton. With those $k-skeleton$ , we can define $X$ to be their direct limit with weak topology to define a CW-complex.

The above discussion may seem technical. But the takeaway is that we view graphs topologically. For folks interested in algebraic topology, I am happy to discuss the definition of CW-complexes in further detail 🙂

Reply
Horace Fusco says:

September 18, 2022 at 6:58 pm

Very thorough and impressive post! I really appreciated your description about the symmetries of a graph. I think it’s nice the way you built up the discussion by beginning with the bare graph and then extending to symmetries that also preserve decorations. One note on the example graph $\Gamma$ is that I believe there is a symmetry that swaps vertices $1$ ad $4$ and fixes $2$ and $3$ since the former two vertices have the same neighbors. Though swapping $1$ and $2$ while fixing $3$ and $4$ would be a problem.

I also liked your illustrations a lot. Having diagrams with color is priceless–maybe some time you can show me how you make those because I haven’t had a ton of success with that in the past.

Reply
- John Eichelberger says:
  
  September 19, 2022 at 3:40 pm
  
  Thanks! I mostly followed the structure of the lecture — it was helpful to start with simple graphs and work our way up. Yes, you’re right about the mistake on the symmetries of the square, a diagonal reflection would swap 1 and 4 while fixing 2 and 3, the correct non-symmetry is what you mentioned.
  
  I take my notes on a tablet — one of the big motivators for getting one was being able to quickly switch colors!
  
  Reply
Michaela Polley says:

September 19, 2022 at 3:47 am

Nice post! Quick formatting note — in the third paragraph under “Groups, reviewed” you forgot to go into math mode, so some of the LaTeX didn’t format correctly. Not a big deal, just letting you know.

I’m still a little bit confused about group actions and the symmetric group for a given set X. Here’s my current understanding: The symmetries of a set X are a subset of configurations of the elements of X. I believe that this is a subset of the automorphisms of X, but am not sure. These symmetries all preserve some feature of the set X that we care about (like “gluing”). Then, a group action comes into play somehow? I think this is where I am getting lost… Any advice would be appreciated!

Reply
- MurphyKate says:
  
  September 19, 2022 at 3:28 pm
  
  In your notation, I think that the symmetries of a *set* X are exactly all of the possible permutations of the elements of X. So Sym(X) = Aut(X). If we want to add in some more structure (so perhaps $X$ is no longer just a set, but a graph, or a labelled graph), we talk about $Sym^+(X)$ . This will be a subgroup of $Sym (X)$ .
  
  Reply
Osip Surdutovich says:

September 19, 2022 at 6:37 am

Great post! I really like the whirlwind section where you list the definitions. They are really clear and when I’ll be doing homework I will use this as a quick reference table to check what we can do! Also the figures are really neat and make a lot of sense!

Reply

First Wednesday: Groups, Graphs, and Symmetries

12 Responses to First Wednesday: Groups, Graphs, and Symmetries

Leave a Reply to Akash Ganguly Cancel reply

Recent Posts

Recent Comments