Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "Burnside's Lemma"

(statement, some background, proof, a sort of clumsy application)
 
m (Link to group action article)
Line 1: Line 1:
−
'''Burnside's Lemma''' is a [[combinatorics |combinatorial]] result in [[group theory]] that is useful for counting the [[orbit]]s 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.
+
'''Burnside's Lemma''' is a [[combinatorics |combinatorial]] result in [[group theory]] that is useful for counting the [[orbit]]s of a [[set]] on which a [[group]] [[group action|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 ==
 
== Statement ==

Revision as of 18:49, 9 September 2008

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.\]

See also

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Burnside%27s_Lemma&oldid=27876"