maths.free › Combinatorics & Graph Theory › Pólya's Enumeration Theorem › Burnside's Lemma

Burnside's Lemma

Burnside's lemmaAgain, not originally proved by Burnside. It was known to Frobenius and for the most part by Cauchy. However, it was most easily found in Burnside's book, and thus his name came to be attached. relates the number of equivalence classes of the action of a group on a finite set to the number of elements of the set fixed by the elements of the group. Before stating and proving it, we need some notation and a proposition. If a group \(G\) acts on a finite set \(\cgC\), let \(\sim\) be the equivalence relation induced by this action. (As before, the action of \(\pi\in G\) on \(\cgC\) will be denoted \(\pi^*\).) Denote the equivalence class containing \(C\in \cgC\) by \(\langle C\rangle\)\(\langle C\rangle\)equivalence class of \(C\). For \(\pi\in G\), let \(\fix_\cgC(\pi)=\{C\in \cgC\colon \pi^*(C) = C\}\), the set of colorings fixed by \(\pi\). For \(C\in\cgC\), let \(\stab_G(C)=\{\pi\in G\colon \pi(C) = C\}\) be the stabilizer\(\stab_G(C)\)stabilizer of \(C\) under action of \(G\) of \(C\) in \(G\), the permutations in \(G\) that fix \(C\).

To illustrate these concepts before applying them, refer back to . Using that information, we can determine that \(\fix_\cgC(r_2) = \{C_1,C_{10},C_{11},C_{16}\}\). Determining the stabilizer of a coloring requires finding the rows of the table in which it appears. Thus, \(\stab_{D_8}(C_7) = \{\iota,h\}\) and \(\stab_{D_8}(C_{11}) = \{\iota,r_2,p,n\}\).

Proposition

Let a group \(G\) act on a finite set \(\cgC\). Then for all \(C\in \cgC\), \[\begin{aligned}\end{aligned}\]

Proof

Let \(\stab_G(C) = \{\pi_1,\dots,\pi_k\}\) and \(T(C,C') = \{\pi\in G\colon \pi^*(C) = C'\}\). (Note that \(T(C,C) = \stab_G(C)\).) Take \(\pi\in T(C,C')\). Then \(\pi\circ \pi_i\in T(C,C')\) for \(1\leq i\leq k\). Furthermore, if \(\pi\circ \pi_i = \pi\circ \pi_j\), then \(\pi^{-1}\circ\pi\circ \pi_i=\pi^{-1}\circ\pi\circ \pi_j\). Thus \(\pi_i=\pi_j\) and \(i=j\). If \(\pi'\in T(C,C')\), then \(\pi\inv\circ \pi'\in T(C,C)\). Thus, \(\pi\inv\circ\pi' = \pi_i\) for some \(i\), and hence \(\pi' = \pi\circ \pi_i\). Therefore \(T(C,C') = \{\pi\circ\pi_1,\dots,\pi\circ\pi_k\}\). Additionally, we observe that \(T(C',C) = \{\pi\inv\colon \pi\in T(C,C')\}\). Now for all \(C'\in\langle C\rangle\), \[\begin{aligned}\end{aligned}\] Therefore, \[\begin{aligned}\end{aligned}\] Now notice that each element of \(G\) appears in \(T(C,C')\) for precisely one \(C'\in\langle C\rangle\), and the proposition follows.

With established, we are now prepared for Burnside's lemma.

Before we proceed to the proof, note that the calculation in Burnside's lemma for the example of \(2\)-coloring the vertices of a square is exactly the calculation we performed at the end of .

Condensed: the full section is in Keller & Trotter, Applied Combinatorics.

Ngayon ikaw Walang kalkulador settles ito isa, ngunit ang mga piraso ng mga ito ay computable. Subukan ang isa sa ibaba, o type ang iyong sarili.

Panatilihin ang iyong sariling nagtatrabaho

Ang isang libreng account ay nagdaragdag ng mga tala sa bawat aralin, isang tala ng kung ano ang iyong natapos, ang iyong mga nalulutas na problema sa isang lugar, at isang guro na maaari mong tanungin tungkol sa pahinang ito. Ang matematika mismo ay bukas sa lahat, naka-sign in o hindi.

Mag-sign Up Mag-login

Mga simbolong ginagamit dito

I-tap ang anumang simbolo para sa buong kahulugan, isang larawan, at kung ano ang ibig sabihin ng bawat titik sa ito.

Mga katanungan na tanong ng mga tao

Permutation or combination?

Ask whether order matters. A lock code is a permutation (order matters); a hand of cards is a combination (it does not).

What is a graph in this sense?

Dots (vertices) joined by lines (edges), not a plot. Road maps, social networks and molecules are graphs; questions like "is there a route" and "how few colours" are graph theory.

Bahagi ng pahinang ito ay naaayon mula sa Keller & Trotter, Applied Combinatorics (CC BY-SA 4.0). Condensed at muling ipinaliwanag dito; errors ay aming.

Higit pa sa Combinatorics & Graph Theory

The counting principles Pigeonhole principle and inclusion, exclusion Binomial coefficients and Pascal's triangle Recurrences and generating functions Graphs: vertices, edges, degrees Paths, cycles, trees, Euler and Hamilton Colouring and planar graphs