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.

Ora tu Nessuna calcolatrice risolve questa domanda, ma le sue parti sono calcolabili. Provane una qui sotto, o digita la tua.

Conserva il tuo lavoro

Un account gratuito aggiunge note su ogni lezione, un record di ciò che hai finito, i tuoi problemi risolti in un unico luogo, e un tutor che puoi chiedere su questa pagina. La matematica stessa è aperta a tutti, firmato o no.

Iscriviti Accesso

Simboli utilizzati qui

Toccare qualsiasi simbolo per la definizione completa, un'immagine, e che cosa ogni lettera in esso significa.

Domande che la gente chiede

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.

Parti di questa pagina sono adattate da Keller & Trotter, Applied Combinatorics (CC BY-SA 4.0). Condensato e ri-spiegato qui; gli errori sono nostri.

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