Burnside's Lemma

From AoPSWiki

Burnside's Lemma is a combinatorial result in group theory that is useful for counting the orbits of a set on which a group acts. The lemma was apparently first stated by Cauchy in 1845. Hence it is also called the Cauchy-Frobenius Lemma, or the lemma that is not Burnside's. The lemma was (mistakenly) attributed to Burnside because he quoted and proved in his 1897 book Theory of groups of finite order without attribution, apparently because he thought it was sufficiently well known.

Statement

Let $G$ be a group acting on a set $S$ . For $\alpha \in G$ , let $\text{fix}(\alpha)$ denote the set of fixed points of $\alpha$ . Then $\lvert G \rvert \cdot \lvert S/G \rvert = \sum_{\alpha \in G} \lvert \text{fix}(\alpha) \rvert .$

Proof. The quantity $\sum_{\alpha \in G} \lvert \text{fix}(\alpha) \rvert$ enumerates the ordered pairs $(\alpha,x) \in G\times S$ for which $\alpha(x)=x$ . Hence $\sum_{\alpha \in G} \lvert \text{fix}(\alpha) \rvert = \lvert \{ (\alpha,x) \in G \times S | \alpha(x) = x \} \rvert = \sum_{x \in S} \lvert \text{stab}(x) \rvert = \sum_{H \in S/G} \sum_{x\in H} \lvert \text{stab}(x) \rvert ,$ where $\text{stab}(x)$ denotes the stabilizer of $x$ .

Without loss of generality, let $G$ operate on $S$ from the left. Now, if $x,y$ are elements of the same orbit, and $g$ is an element of $G$ such that $g(x)=y$ , then the mapping $\alpha \mapsto g \alpha g^{-1}$ is a bijection from $\text{stab}(x)$ onto $\text{stab}(y)$ . It then follows from the orbit-stabilizer theorem that for any $i$ in an orbit $H$ of $S$ , $\sum_{x\in H} \lvert \text{stab}(x) \rvert = \sum_{x\in H} \lvert \text{stab}(i) \rvert = \lvert \text{orb}(i) \rvert \cdot \lvert \text{stab}(i) \rvert = \lvert G \rvert .$ Therefore $\sum_{\alpha \in G} \lvert \text{fix}(\alpha) \rvert = \sum_{H \in S/G} \sum_{x\in H} \lvert \text{stab}(x) \rvert = \sum_{H \in S/G} \lvert G \rvert = \lvert G \rvert \cdot \lvert S/G \rvert,$ as desired. $\blacksquare$

Application

The theorem is primarily of use when $G$ and $S$ are finite. Here, it is useful for counting the orbits of $S$ . This can be useful when one wishes to know the number of distinct objects of some sort up to a certain class of symmetry.

For instance, the lemma can be used to count the number of non-isomorphic graphs on $n$ vertices. As an example, we count the number of non-isomorphic graphs on 4 vertices.

Consider the action symmetric group on the four vertices induced on their graphs. Two graphs are isomorphic if and only if they lie in the same orbit. The elements of this symmetric group and the number of fixed points they have are as follows:

The identity, $e$ . Every graph is a fixed point of this; there are $\binom{4}{2}$ possible edges, so $\text{fix}(e) = 2^{\binom{4}{2}} = 2^6 = 64$ .
The two-cycles, of which there are $\binom{4}{2}=6$ . If a graph is invariant under a two-cycle $(ab)$ , then vertices $c$ and $a$ are connected if and only if vertices $c$ and $b$ are connected. It follows that there are $2^{1+ \binom{3}{2}} = 2^4 = 16$ fixed points here.
Compositions of two disjoint two-cycles, of which there are 3. In this case, we have 16 fixed points.
Three-cycles, of which there are 8. Here, either the three cycling vertices are connected, or they are not; and the fixed vertex is either connected to the others, or it is not. This gives 4 fixed points for each three-cycle.
Permutations with exactly one orbit, i.e., derangements other than compositions of disjoint two-cycles. There are 6 of these. Here we have 4 fixed points.

It then follows that the number of non-isomorphic graphs on 4 vertices is $\frac{1}{\lvert S_4 \rvert} \sum_{\sigma \in S_4} \lvert \text{fix}(\sigma) \rvert = \frac{1}{24} ( 1\cdot 64 + 6\cdot 16 + 3 \cdot 16 + 8 \cdot 4 + 6 \cdot 4) = 11.$

Personal tools

Navigation

Search

Toolbox

Burnside's Lemma

From AoPSWiki

Statement

Application

See also