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.

Teraz ty Žiadna kalkulačka túto rovnicu nevyrieši, ale jej časti sú vypočítateľné.Skúste niektorú z nižšie uvedených, alebo napíšte vlastnú.

Udržujte svoje vlastné pracovné

Bezplatný účet pridáva poznámky ku každej lekcii, záznam o tom, čo ste dokončili, vaše vyriešené problémy na jednom mieste, a učiteľa, ktorého sa môžete opýtať na túto stránku.Math samotná je otvorená pre každého, prihlásený alebo nie.

Zaregistrovať sa Prihlásenie

Symboly použité tu

Ťuknutím na ľubovoľný symbol zobrazíte úplnú definíciu, obrázok a význam každého písmena.

Otázky, ktoré ľudia kladú

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.

Časti tejto stránky sú upravené z Keller & Trotter, Applied Combinatorics (CC BY-SA 4.0). Tu sú zhrnuté a znovu vysvetlené; chyby sú naše.

Viac v kategórii 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