Mar '26 Notes

This is my third set of monthly notes for this year. In these notes, I capture various interesting pieces of information and facts I have stumbled upon during the month. Like in the last two months, I have been learning and exploring algebraic graph theory. There are mainly two books I have been reading: one by Godsil and Royle and another by Norman Biggs, both titled Algebraic Graph Theory. So most of my notes come from my study of these books.

Right Group Action

Let \( G \) be a group with identity element \( e. \) Let \( X \) be a set. A right action of \( G \) on \( X \) is a map \[ \alpha : X \times G \to X \] such that \begin{align*} \alpha(x, e) &= x, \\ \alpha(\alpha(x, g), h) &= \alpha(x, gh) \end{align*} for all \( x \in X \) and all \( g, h \in G. \)

The two conditions above are called the identity and compatibility properties of the group action. If we denote \( \alpha(x, g) \) as \( x^g, \) then the notation for the two conditions can be simplified to \( x^e = x \) and \( (x^g)^h = x^{gh} \) for all \( g, h \in G. \)

Group Action Example

Take \( G = \mathbb{Z}_3 \) be the group under adddition modulo \( 3 . \) Then take \( X = \{ 1, 2, 3, 4, 5, 6 \}. \) Define the action by \[ x^g = \begin{cases} 1 + ((x - 1 + g) \bmod{3}) & \text{if } x \in \{ 1, 2, 3 \}, \\ 4 + ((x - 4 + g) \bmod{3}) & \text{if } x \in \{ 4, 5, 6 \} \end{cases} \] Now \( G \) acts on \( X. \) Each \( g \in G \) acts as a permutation of the elements of \( X. \) For example, the element \( 0 \in \mathbb{Z}_3 \) is the identity permutation. The element \( 1 \in \mathbb{Z}_3 \) acts as the permutation \( (1 2 3) (4 5 6). \) The element \( 2 \in \mathbb{Z}_3 \) acts as \( (1 3 2) (4 6 5). \) This action splits \( X \) into two orbits \( \{ 1, 2, 3 \} \) and \( \{ 4, 5, 6 \}. \)

Group Actions as Permutations

We saw an example of a group action and observed that each element of the group acts as a permutation. That wasn't merely a coincidence. It is indeed a general property of group actions. Whenever a group \( G \) acts on a set \( X, \) each element \( g \in G \) determines a bijection \( X \to X. \) In other words, every element of \( G \) acts as a permutation of the elements of \( X. \) Let us see why this must be the case.

Let \( G \) act on a set \( X. \) Let \( g \in G. \) Define a map \[ \alpha: X \to X; \; x \mapsto x^g. \] We show that \( \alpha \) is a bijection. First we prove injectivity. Suppose \( x^g = y^g. \) Then \begin{align*} (x^g)^{g^{-1}} = (y^g)^{g^{-1}} & \implies x^{g g^{-1}} = y^{g g^{-1}} \\ & \implies x^e = y^e \\ & \implies x = y. \end{align*} This completes the proof of injectivity. Note that the first and last implications follow respectively from the compatibility and identity properties of the group action. Now we prove surjectivity. Let \( y \in X. \) Take \( x = y^{g^{-1}}. \) Then \[ x^g = (y^{g^{-1}})^g = y^{g^{-1} g} = y^e = y. \] Thus every element \( y \in X \) has a preimage. Hence \( \alpha \) is surjective. Since we have already shown that \( \alpha \) is injective, we now conclude that \( \alpha \) is bijective.

Orbit-Stabiliser Theorem

TODO.

Stabiliser Index

In a vertex-transitive graph \( \Gamma, \) for any vertex \( x \in V(\Gamma), \) the index of the stabiliser \( G_x \) in \( G = \operatorname{Aut}(\Gamma) \) is given by the equation \[ \frac{\lvert G \rvert}{\lvert G_x \rvert} = \lvert V(\Gamma) \rvert. \] This follows directly from the orbit-stabiliser theorem.