Subbab 16.2 Teori Himpunan Ekstremal

Misalkan \(n\) bilangan bulat positif dan \([n]=\{1,2,\dots,n\}\text{.}\) Dalam bagian ini, kita meninjau masalah-masalah dengan bentuk umum berikut: berapakah ukuran maksimum suatu keluarga subhimpunan \([n]\) apabila keluarga tersebut harus memenuhi sifat-sifat tertentu?

Berikut sebuah contoh elementer.

Contoh 16.6.

Ukuran maksimum keluarga \(\cgF\) subhimpunan \([n]\) yang memenuhi \(A\cap B\neq\emptyset\) untuk semua \(A,B\in\cgF\) adalah \(2^{n-1}\text{.}\)

Untuk batas bawah, tinjau keluarga \(\cgF\) yang terdiri atas semua subhimpunan \([n]\) yang memuat \(1\text{.}\) Jelas bahwa keluarga ini mempunyai \(2^{n-1}\) anggota dan setiap dua himpunan dalam keluarga tersebut memiliki irisan tak kosong.

Untuk batas atas, misalkan \(\cgF\) keluarga subhimpunan yang setiap pasangan himpunan dalam \(\cgF\) memiliki irisan tak kosong. Setiap kali suatu subhimpunan \(S\) merupakan anggota \(\cgF\text{,}\) komplemen \(S'\) dari \(S\) tidak dapat termasuk dalam \(\cgF\text{.}\) Karena seluruh keluarga yang terdiri atas semua \(2^n\) subhimpunan \([n]\) dapat dipandang sebagai \(2^{n-1}\) pasangan saling berkomplemen, dan paling banyak satu himpunan dari setiap pasangan dapat termasuk dalam \(\cgF\text{,}\) kita menyimpulkan bahwa \(|\cgF|\le 2^{n-1}\text{.}\)

Sebagai contoh kedua, kita dapat meninjau kembali Teorema Sperner dari Bab 6 dan menyatakan ulang hasilnya sebagai berikut.

Contoh 16.7.

Ukuran maksimum keluarga \(\cgF\) subhimpunan \([n]\) dengan syarat bahwa, jika \(A\) dan \(B\) merupakan dua himpunan berbeda dalam \(\cgF\text{,}\) tidak satu pun menjadi subhimpunan yang lain, adalah \(\binom{n}{\lfloor n/2\rfloor}\text{.}\)

Perlu dicatat bahwa dalam Contoh 16.7 hanya ada sangat sedikit keluarga ekstremal (satu atau dua), i.e., jika \(\cgF\) merupakan keluarga subhimpunan \([n]\text{,}\) \(|\cgF|= \binom{n}{\lfloor n/2\rfloor}\text{,}\) dan tidak ada himpunan dalam \(\cgF\) yang menjadi subhimpunan sejati dari himpunan lainnya, maka \(\cgF=\{S\subseteq[n]: |S|=\lfloor n/2\rfloor\}\) atau \(\cgF=\{S\subseteq[n]: |S|=\lceil n/2\rceil\}\text{.}\) Tentu saja, ketika \(n\) genap, keduanya merupakan keluarga yang persis sama.

Di sisi lain, terdapat banyak keluarga ekstremal bagi Contoh 16.6, sebab salah satu anggota dari setiap pasangan himpunan saling berkomplemen dapat dipilih.

Kita menutup pengantar singkat tentang teori himpunan ekstremal ini dengan sebuah hasil klasik.

Teorema 16.8. Erdős, Ko, Rado.

Misalkan \(n\) dan \(k\) bilangan bulat positif dengan \(n\ge 2k\text{.}\) Ukuran maksimum keluarga \(\cgF\) subhimpunan \([n]\) yang memenuhi syarat (1) \(A\cap B\neq\emptyset\) untuk semua \(A,B\in\cgF\text{,}\) dan (2) \(|A|=k\) untuk semua \(A\in\cgF\text{,}\) adalah \(\binom{n-1}{k-1}\text{.}\)

Bukti.

Untuk batas bawah, tinjau keluarga \(\cgF\) yang terdiri atas semua subhimpunan berukuran \(k\) dari \([n]\) yang memuat \(1\text{.}\)

Untuk batas atas, misalkan \(\cgF\) keluarga subhimpunan \([n]\) yang memenuhi kedua syarat tersebut. Kita menunjukkan bahwa \(|\cgF|\le\binom{n-1}{k-1}\text{.}\) Untuk melakukannya, tinjau sebuah lingkaran pada bidang Euklides dengan \(n\) titik \(p_1\text{,}\) \(p_2,\dots,p_n\) yang berjarak sama di sepanjang kelilingnya. Terdapat \(n!\) cara berbeda, satu bagi setiap permutasi \(\sigma\) dari \([n]\text{,}\) untuk menempatkan bilangan-bilangan dalam \([n]\) secara satu-ke-satu pada titik-titik dalam \(\{p_1,p_2,\dots,p_n\}\text{.}\)

Untuk setiap permutasi \(\sigma\) dari \([n]\text{,}\) misalkan \(\cgF(\sigma)\) menyatakan subkeluarga \(\cgF\) yang terdiri atas semua himpunan \(S\) dalam \(\cgF\) yang elemen-elemennya menempati satu blok berurutan di sekeliling lingkaran. Selanjutnya, misalkan \(t=\sum_\sigma|\cgF(\sigma)|\text{.}\)

Klaim pertama kita adalah \(t\le kn!\text{.}\) Untuk membuktikannya, misalkan \(\sigma\) suatu permutasi dan andaikan \(|\cgF(\sigma)|=s \ge 1\text{.}\) Gabungan himpunan-himpunan dalam \(\cgF(\sigma)\) merupakan himpunan titik yang membentuk blok berurutan pada lingkaran. Karena \(n\ge 2k\text{,}\) perhatikan bahwa blok ini tidak mencakup seluruh lingkaran. Oleh karena itu, terdapat himpunan \(S\) yang elemen-elemennya merupakan \(k\) titik pertama, menurut arah jarum jam, di dalam blok ini. Karena setiap himpunan lain dalam \(\cgF(\sigma)\) merupakan pergeseran sebanyak satu posisi atau lebih menurut arah jarum jam, segera diperoleh \(|\cgF(\sigma)|\le k\text{.}\) Karena terdapat \(n!\) permutasi, klaim tersebut terbukti.

Sekarang kita mengklaim bahwa bagi setiap himpunan \(S\in\cgF\text{,}\) terdapat tepat \(n k!(n-k)!\) permutasi \(\sigma\) yang memenuhi \(S\in\cgF(\sigma)\text{.}\) Perhatikan bahwa terdapat \(n\) posisi di sekeliling lingkaran, dan masing-masing dapat menjadi titik pertama dalam blok berisi \(k\) posisi berurutan tempat elemen-elemen \(S\) diletakkan. Selanjutnya, terdapat \(k!\) cara mengurutkan elemen-elemen \(S\) dan \((n-k)!\) cara mengurutkan elemen-elemen yang tersisa. Hal ini membuktikan klaim kita.

Untuk menyelesaikan bukti teorema, perhatikan bahwa

\begin{equation*} |\cgF| n k! (n-k)!= t\le k n!, \end{equation*}

dan ini menyiratkan bahwa \(|\cgF|\le\binom{n-1}{k-1}\text{.}\)

Sblm Ke Atas Lnjt