Difference between revisions of "Burnside's Lemma"
(statement, some background, proof, a sort of clumsy application) |
(→History) |
||
| (4 intermediate revisions by 4 users not shown) | |||
| 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]]. |
| + | |||
| + | == History == | ||
| + | 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 it in his 1897 book ''Theory of groups of finite order'' without attribution, apparently because he thought it was sufficiently well known. | ||
== Statement == | == Statement == | ||
| Line 41: | Line 44: | ||
[[Category:Group theory]] | [[Category:Group theory]] | ||
[[Category:Combinatorics]] | [[Category:Combinatorics]] | ||
| + | [[Category:Theorems]] | ||
| + | [[Category:Mathematics]] | ||
| + | [[Category:Abstract algebra]] | ||
Latest revision as of 23:16, 18 November 2024
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.
Contents
History
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 it in his 1897 book Theory of groups of finite order without attribution, apparently because he thought it was sufficiently well known.
Statement
Let 
be a group acting on a set 
. For 
, let 
denote the set of fixed points of 
. Then
![\[\lvert G \rvert \cdot \lvert S/G \rvert = \sum_{\alpha \in G} \lvert \text{fix}(\alpha) \rvert .\]](http://latex.artofproblemsolving.com/b/f/9/bf9602a5fdaa617bab7bc7f7fb60272ebf26f1f1.png)
Proof. The quantity 
enumerates the ordered pairs 
for which 
. 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 ,\]](http://latex.artofproblemsolving.com/f/9/8/f98eb8843ccf4be55aef291c3da2bae2639a7a2d.png)
where 
denotes the stabilizer of 
.
Without loss of generality, let operate on from the left. Now, if 
are elements of the same orbit, and 
is an element of such that 
, then the mapping 
is a bijection from onto 
. It then follows from the orbit-stabilizer theorem that for any 
in an orbit 
of ,
![\[\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 .\]](http://latex.artofproblemsolving.com/e/a/3/ea3eb27d869535f9213eb79050cedb605ab6de3f.png)
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,\]](http://latex.artofproblemsolving.com/9/3/a/93abaf57d2d8d7ede20cfc4002dc0695917594ef.png)
as desired. 
Application
The theorem is primarily of use when and are finite. Here, it is useful for counting the orbits of . 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 
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,
. Every graph is a fixed point of this; there are 
possible edges, so 
. - The two-cycles, of which there are
. If a graph is invariant under a two-cycle 
, then vertices 
and 
are connected if and only if vertices and 
are connected. It follows that there are 
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.
. Every graph is a fixed point of this; there are 
possible edges, so 
.
. If a graph is invariant under a two-cycle 
, then vertices 
and 
are connected if and only if vertices 
are connected. It follows that there are 
fixed points here.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.\]](http://latex.artofproblemsolving.com/3/1/4/31484adfd249e1b174bd25bdce5aa08f507a3ab0.png)
