Proposisi 15.8.
Misalkan suatu grup \(G\) bertindak pada himpunan hingga \(\cgC\text{.}\) Maka, untuk setiap \(C\in \cgC\text{,}\)
\begin{equation*}
\sum_{C'\in\langle C\rangle} |\stab_G(C')| = |G|.
\end{equation*}
Subbab 15.3 Lemma Burnside
Lemma Burnside menghubungkan banyak kelas ekuivalensi dari aksi suatu grup pada himpunan hingga dengan banyak elemen himpunan yang ditetapkan oleh elemen-elemen grup tersebut. Sebelum menyatakan dan membuktikannya, kita memerlukan beberapa notasi dan sebuah proposisi. Jika suatu grup \(G\) bertindak pada himpunan hingga \(\cgC\text{,}\) misalkan \(\sim\) merupakan relasi ekuivalensi yang diinduksi oleh aksi tersebut. (Seperti sebelumnya, aksi \(\pi\in G\) pada \(\cgC\) dinyatakan dengan \(\pi^*\text{.}\)) Nyatakan kelas ekuivalensi yang memuat \(C\in \cgC\) dengan \(\langle C\rangle\). Untuk \(\pi\in G\text{,}\) misalkan \(\fix_\cgC(\pi)=\{C\in \cgC\colon \pi^*(C) = C\}\text{,}\) yaitu himpunan pewarnaan yang ditetapkan oleh \(\pi\text{.}\) Untuk \(C\in\cgC\text{,}\) misalkan \(\stab_G(C)=\{\pi\in G\colon \pi(C) = C\}\) merupakan penstabil dari \(C\) dalam \(G\text{,}\) yakni permutasi-permutasi dalam \(G\) yang menetapkan \(C\text{.}\)
1
Sekali lagi, hasil ini mula-mula bukan dibuktikan oleh Burnside. Hasil tersebut telah diketahui oleh Frobenius dan sebagian besar juga oleh Cauchy. Namun, hasil itu paling mudah ditemukan dalam buku Burnside, sehingga namanya kemudian melekat.
Untuk menggambarkan konsep-konsep ini sebelum menerapkannya, lihat kembali Gambar 15.2. Berdasarkan informasi tersebut, kita dapat menentukan bahwa \(\fix_\cgC(r_2) = \{C_1,C_{10},C_{11},C_{16}\}\text{.}\) Untuk menentukan penstabil suatu pewarnaan, kita perlu mencari baris-baris tabel tempat pewarnaan itu muncul. Jadi, \(\stab_{D_8}(C_7) = \{\iota,h\}\) dan \(\stab_{D_8}(C_{11}) = \{\iota,r_2,p,n\}\text{.}\)
Bukti.
Misalkan \(\stab_G(C) = \{\pi_1,\dots,\pi_k\}\) dan \(T(C,C') = \{\pi\in G\colon \pi^*(C) = C'\}\text{.}\) (Perhatikan bahwa \(T(C,C) = \stab_G(C)\text{.}\)) Ambil \(\pi\in T(C,C')\text{.}\) Maka \(\pi\circ \pi_i\in T(C,C')\) untuk \(1\leq i\leq k\text{.}\) Selain itu, jika \(\pi\circ \pi_i = \pi\circ \pi_j\text{,}\) maka \(\pi^{-1}\circ\pi\circ \pi_i=\pi^{-1}\circ\pi\circ \pi_j\text{.}\) Jadi, \(\pi_i=\pi_j\) dan \(i=j\text{.}\) Jika \(\pi'\in T(C,C')\text{,}\) maka \(\pi\inv\circ \pi'\in T(C,C)\text{.}\) Dengan demikian, \(\pi\inv\circ\pi' = \pi_i\) untuk suatu \(i\text{,}\) sehingga \(\pi' = \pi\circ \pi_i\text{.}\) Oleh karena itu, \(T(C,C') = \{\pi\circ\pi_1,\dots,\pi\circ\pi_k\}\text{.}\) Selain itu, kita mengamati bahwa \(T(C',C) = \{\pi\inv\colon \pi\in T(C,C')\}\text{.}\) Sekarang, untuk setiap \(C'\in\langle C\rangle\text{,}\)
\begin{equation*}
|\stab_G(C')|=|T(C',C')|=|T(C',C)| =
|T(C,C')| = |T(C,C)| = |\stab_G(C)|.
\end{equation*}
Oleh karena itu,
\begin{equation*}
\sum_{C'\in\langle C\rangle}|\stab_G(C')| =
\sum_{C'\in\langle C\rangle} |T(C,C')|.
\end{equation*}
Perhatikan bahwa setiap elemen \(G\) muncul dalam \(T(C,C')\) untuk tepat satu \(C'\in\langle C\rangle\text{.}\) Dengan demikian, proposisi terbukti.
Setelah Proposisi 15.8 dibuktikan, kita siap membahas lemma Burnside.
Lema 15.9. Lemma Burnside.
Misalkan suatu grup \(G\) bertindak pada himpunan hingga \(\cgC\text{.}\) Jika \(N\) merupakan banyak kelas ekuivalensi \(\cgC\) yang diinduksi oleh aksi tersebut, maka
\begin{equation*}
N = \frac{1}{|G|} \sum_{\pi\in G} |\fix_\cgC(\pi)|.
\end{equation*}
Sebelum melanjutkan ke pembuktian, perhatikan bahwa perhitungan dalam lemma Burnside untuk contoh pewarnaan-\(2\) simpul-simpul persegi tepat sama dengan perhitungan yang dilakukan pada akhir Subbab 15.1.
Bukti.
Misalkan \(X=\{(\pi,C)\in G\times \cgC\colon \pi(C) = C\}\text{.}\) Perhatikan bahwa \(\sum_{\pi \in G} |\fix_\cgC(\pi)| = |X|\text{,}\) sebab setiap suku dalam jumlah tersebut menghitung banyak pasangan terurut dalam \(X\) yang mempunyai \(\pi\) sebagai koordinat pertama. Demikian pula, \(\sum_{C\in \cgC} |\stab_G(C)| = |X|\text{,}\) dengan setiap suku menghitung banyak pasangan terurut dalam \(X\) yang mempunyai \(C\) sebagai koordinat kedua. Jadi, \(\sum_{\pi \in G} |\fix_\cgC(\pi)|=\sum_{C\in \cgC} |\stab_G(C)|\text{.}\) Perhatikan bahwa jumlah terakhir dapat ditulis kembali sebagai
\begin{equation*}
\sum_{\substack{\text{equivalence} \\\text{classes } \langle
C\rangle} }\left( \sum_{C'\in\langle C\rangle}
|\stab_G(C')|\right).
\end{equation*}
Berdasarkan Proposisi 15.8, jumlah bagian dalam ialah \(|G|\text{.}\) Oleh karena itu, jumlah keseluruhannya ialah \(N\cdot |G|\text{.}\) Dengan menyelesaikan persamaan terhadap \(N\text{,}\) kita memperoleh persamaan yang diinginkan.
Lemma Burnside mengesahkan perhitungan yang kita lakukan pada bagian sebelumnya. Namun, bagaimana jika kita bekerja dengan segi enam, bukan persegi, dan mengizinkan empat warna, bukan dua? Akan terdapat \(4^6=4096\) pewarnaan berbeda, sedangkan grup dihedral segi enam mempunyai \(12\) elemen. Menyusun tabel analog dengan Gambar 15.2 dalam keadaan ini tentu sangat merepotkan! Di sinilah kecemerlangan pendekatan Pólya berperan, seperti yang akan kita lihat pada bagian berikutnya.
