Teorema 6.27. Teorema Sperner.
Untuk setiap \(t\ge1\text{,}\) lebar kisi subhimpunan \(\bftwo^t\) sama dengan ukuran terbesar suatu peringkat, i.e.,
\begin{equation*}
\width(\bftwo^t)=\binom{t}{\lfloor\frac{t}{2}\rfloor}\text{.}
\end{equation*}
Subbab 6.5 Kisi Subhimpunan
Jika \(X\) merupakan himpunan berhingga, keluarga semua subhimpunan \(X\text{,}\) yang terurut parsial oleh inklusi, membentuk kisi subhimpunan. Hal ini diilustrasikan pada Gambar 6.26, yang menampilkan kisi semua subhimpunan \(\{1,2,3,4\}\text{.}\) Perhatikan bahwa pada gambar tersebut, himpunan direpresentasikan dengan string bit. Notasinya disingkat lagi dengan menuliskan string itu tanpa koma dan tanda kurung.
1
Suatu kisi merupakan jenis poset khusus. Anda tidak perlu mempelajari definisinya di sini; selama membaca bab ini, Anda dapat mengganti istilah “kisi” dengan “poset” tanpa mengubah pembahasan.
Diagram Hasse kisi 16 subhimpunan dari himpunan berelemen empat, yang dilabeli dengan string bit. String 0000 berada di bawah, string 1111 berada di atas, dan setiap sisi menghubungkan dua string yang berbeda tepat pada satu bit.
Untuk bilangan bulat positif \(t\text{,}\) \(\bftwo^t\) menyatakan kisi subhimpunan yang terdiri atas semua subhimpunan \(\{1,2,\dots,t\}\) dan terurut oleh inklusi. Beberapa sifat dasar poset ini adalah sebagai berikut:
-
Tingginya adalah \(t+1\text{,}\) dan setiap rantai maksimal memiliki tepat \(t+1\) titik.
-
Ukuran poset \(\bftwo^t\) adalah \(2^t\text{,}\) dan elemen-elemennya terpartisi menjadi peringkat-peringkat (antirantai) \(A_0, A_1,\dots, A_t\) dengan \(|A_i|=\binom{t}{i}\) untuk setiap \(i=0,1,\dots,t\text{.}\)
-
Peringkat berukuran terbesar pada kisi subhimpunan terletak di tengah, i.e. jika \(s=\lfloor t/2\rfloor\text{,}\) maka koefisien binomial terbesar dalam barisan \(\binom{t}{0}, \binom{t}{1},\binom{t}{2},\dots,\binom{t}{t}\) adalah \(\binom{t}{s}\text{.}\) Perhatikan bahwa jika \(t\) ganjil, ada dua peringkat berukuran terbesar, sedangkan jika \(t\) genap, hanya ada satu.
Subbagian 6.5.1 Teorema Sperner
Untuk lebar kisi subhimpunan, berlaku hasil klasik berikut dari Sperner.
Bukti.
Lebar poset \(\bftwo^t\) sekurang-kurangnya \(C(t,\lfloor\frac{t}{2}\rfloor)\) karena himpunan semua subhimpunan berelemen \(\lfloor\frac{t}{2}\rfloor\) dari \(\{1,2,\dots,t\}\) merupakan antirantai. Sekarang akan ditunjukkan bahwa lebar \(\bftwo^t\) paling besar \(C(t,\lfloor\frac{t}{2}\rfloor)\text{.}\)
Misalkan \(w\) adalah lebar \(\bftwo^t\) dan \(\{S_1,S_2,\dots, S_w\}\) merupakan antirantai berukuran \(w\) dalam poset ini, i.e., setiap \(S_i\) merupakan subhimpunan dari \(\{1,2,\dots,t\}\text{,}\) dan jika \(1\le i\lt j\le w\text{,}\) maka \(S_i\nsubseteq S_j\) dan \(S_j\nsubseteq S_i\text{.}\)
Untuk setiap \(i\text{,}\) perhatikan himpunan \(\cgS_i\) yang terdiri atas semua rantai maksimal yang melalui \(S_i\text{.}\) Mudah dilihat bahwa jika \(|S_i|=k_i\text{,}\) maka \(|\cgS_i|=k_i!(t-k_i)!\text{.}\) Untuk membentuk rantai terbesar semacam itu dengan \(S_i\) sebagai titik antara, elemen-elemen \(S_i\) dihapus satu per satu sehingga terbentuk himpunan-himpunan pada bagian bawah rantai. Selanjutnya, bagian atas rantai dibentuk dengan menambahkan satu per satu elemen yang tidak berada dalam \(S_i\text{.}\)
Perhatikan pula bahwa jika \(1\le i \lt j\le w\text{,}\) maka \(\cgS_i\cap \cgS_j =\emptyset\text{.}\) Sebab, jika ada rantai terbesar yang termasuk dalam \(\cgS_i\) sekaligus \(\cgS_j\text{,}\) salah satu di antara \(S_i\) dan \(S_j\) tentu merupakan subhimpunan dari yang lain.
Secara keseluruhan, terdapat tepat \(t!\) rantai terbesar dalam \(\bftwo^t\text{.}\) Oleh karena itu,
\begin{equation*}
\sum_{i=1}^{w} k_i!(t-k_i)!\le t!\text{.}
\end{equation*}
Akibatnya,
\begin{equation*}
\sum_{i=1}^{w}\frac{k_i!(t-k_i)!}{t!}=
\sum_{i=1}^{w}\frac{1}{\binom{t}{k_i}}\le 1.
\end{equation*}
Dengan demikian,
\begin{equation*}
\sum_{i=1}^{w}\frac{1}{\binom{t}{\lceil\frac{t}{2}\rceil}}\le 1\text{.}
\end{equation*}
Jadi,
\begin{equation*}
w\le \binom{t}{\lceil\frac{t}{2}\rceil}\text{.}
\end{equation*}
