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 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