Burnside's Lemma
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
[hide]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
Proof. The quantity enumerates the ordered pairs for which . Hence 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 , Therefore 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.
It then follows that the number of non-isomorphic graphs on 4 vertices is