Tagged: clique

Pintu Rahasia Teorema Graf Ekstremal: sebuah pendekatan probabilistik

Teori graf ekstremal merupakan salah satu cabang ilmu teori graf yang berkembang paling pesat pada masanya. Pada dasarnya, bidang ini menyelidiki batasan-batasan parameter dari suatu graf ketika kepadanya kita terapkan suatu sifat tertentu (extremal property). Disiplin ilmu ini pertama kali dipopulerkan oleh Paul Turán, seorang matematikawan terkemuka Hungaria, dengan melontarkan sebuah pertanyaan yang pada akhirnya menjadi suatu penyelidikan yang sangat menarik di kalangan kaum akademisi pada saat itu.

Pertanyaan tersebut adalah: jika diketahui sebuah graf G dengan orde (banyak titik) n tidak memiliki K_q sebagai subgraf, berapakah ukuran (banyak sisi) maksimum yang mungkin untuk G? Jika q=3, maka pertanyaan tersebut akan mencari ukuran terbesar suatu graf yang tidak memuat segitiga. Dengan cepat mungkin kita akan membayangkan graf bipartit sebagai graf tanpa segitiga. Untuk menampung sebanyak mungkin sisi, kita buat bipartit ini menjadi bipartit lengkap dengan ukuran kelas partisi serata mungkin. Tentu semua graf bipartit tidak memuat segitiga, namun apakah kita yakin bahwa tidak ada struktur graf lain yang sama-sama tidak memuat segitiga, namun bisa lebih padat dari bipartit lengkap? Jauh sebelum Turán, pada tahun 1907 Mantel telah membuktikan bahwa jawaban atas pertanyaan tadi adalah ya. Masalah yang menjadi titik perhatian Turán adalah perumuman masalah Mantel. Menariknya, solusi masalah tersebut rupanya juga merupakan perumuman langsung dari solusi Mantel.

Dalam graf (q-1)-ary lengkap, yaitu graf dengan q-1 kelas partisi titik dan ada sisi di antara dua titik jika dan hanya jika kedua titik berada di kelas yang berbeda, kita dapat yakin bahwa di dalamnya tidak mungkin termuat subgraf lengkap dengan q titik. Namun demikian, Turán juga menyatakan bahwa tidak ada graf lain yang lebih padat dari graf (q-1)-ary yang memiliki sifat yang sedang kita cari. Temuan Turán ini menjadi dasar yang mengukuhkan teori graf ekstremal dan untuk mengapresiasi mahakaryanya, graf ektremal ini dinamai atas nama keluarganya. Graf Turán dengan n titik adalah graf (q-1)-ary lengkap dengan kelas partisi dengan kardinalitas n_1,n_2,\dots,n_{q-1} di mana |n_i-n_j|\le 1 untuk setiap i\neq j. Atau dengan kata lain, kita membagi n titik dalam graf tersebut ke dalam q-1 kelas serata mungkin dan membangkitkan sisi dari sembarang titik dari dua kelas yang berbeda. Berapakah ukuran graf Turán? Jika n habis dibagi q-1, maka kita dapat memilih ukuran kelas partisi yang uniform, yaitu n_i=n/(q-1) dan kemudian graf tersebut akan memiliki sisi sebanyak {q-1 \choose 2} (n/(q-1))^2=(1-1/(q-1))n^2/2. Ini merupakan nilai ekstremal dari ukuran graf tanpa subgraf lengkap K_q. Secara formal, Teorema Turán berkata sebagai berikut.

Jika G graf dengan n titik tidak memiliki K_q sebagai subgraf (q\ge 2), maka

|E(G)| \le \left(1-\dfrac{1}{q-1}\right) \dfrac{n^2}{2}

Turán membuktikan teoremanya dengan argumen induksi, yang (mengejutkannya) cukup sederhana. Namun demikian, yang membuatnya makin menarik adalah bukti probabilistik yang diberikan oleh Noga Alon, kombinatorikawan Israel dan Joel Spencer, kombinatorikawan Amerika Serikat dalam buku mereka, “The Probabilistic Methods”. Aigner dan Ziegler mempertimbangkan bukti Alon & Spencer sebagai bukti yang “berasal dari sang buku” (proof from the book), suatu legenda mengenai kumpulan bukti & argumen matematika yang ‘cantik’ yang dipopulerkan oleh Paul Erdos.

Walaupun sampai saat ini pembuktikan masalah kombinatorik dengan teknik probabilistik sudah sangat populer, bukti Alon & Spencer ini masih cukup mengejutkan, karena argumen mereka berangkat dari suatu titik yang sama sekali tidak terlihat ada kaitannya dengan masalah ekstremal ini. Dan karenanya, bukti ini layak untuk meraih gelar “berasal dari sang buku”. Pada dasarnya, bukti ini akan menggunakan sifat linearitas ekspektasi, ketidaksamaan Cauchy-Schwarz, dan lema jabat tangan teori graf. Berikut merupakan bukti Alon-Spencer untuk teorema Turán.

Bukti:

Pertama, kita definisikan bilangan clique dari suatu graf G, dinotasikan \omega(G), yaitu bilangan bulat positif q terbesar sehingga K_q merupakan subgraf dari G. Misalkan G graf dengan himpunan titik \{v_1,\dots,v_n\} dan titik v_i memiliki derajat d_i. Kita akan terlebih dahulu membuktikan suatu klaim, yaitu

\omega(G) \ge \sum\limits_{k=1}^n \dfrac{1}{n-d_i}

Untuk membuktikan klaim ini, kita akan membangun suatu ruang peluang. Misalkan \sigma adalah suatu n-permutasi acak yang dipilih secara uniform, artinya setiap n-permutasi muncul dengan peluang 1/n!. Kemudian, kita definisikan himpunan (acak) A_\sigma di mana titik v_{\sigma (j)}\in A_\sigma jika dan hanya jika v_{\sigma (j)} bertetangga dengan v_{\sigma (i)} untuk semua i<j. Berdasarkan definisi ini, titik-titik di A_\sigma membentuk subgraf lengkap di G. Selanjutnya, kita akan mencari rata-rata kardinalitas A_\sigma. Misalkan X merupakan peubah acak kardinalitas A_\sigma dan X_i adalah peubah acak indikator v_i \in A_\sigma. Ekspektasi X_i bernilai sama dengan peluang kejadian v_i \in A_\sigma. Perhatikan bahwa v_i \in A_\sigma jika dan hanya jika dalam \sigma, v_i muncul sebelum semua titik yang tidak bertetangga dengannya (ada n-1-d_i titik). Untuk memilih urutan posisi d_i tetangga v_i, ada [n]_{d_i} cara. Setelah itu, kita posisikan v_i pada posisi pertama yang belum ditempati oleh tetangga-tetangga v_i. Baru setelah itu, kita dapat dengan bebas mengatur posisi n-1-d_i titik sisanya dan terdapat (n-1-d_i)! cara untuk mengaturnya. Ini berarti bahwa \mathbb{E}X_i= [n]_{d_i} (n-1-d_i)! /n! = 1/(n-d_i). Selanjutnya, berdasarkan sifat linearitas ekspektasi, kita dapat simpulkan bahwa

\mathbb{E}X=\sum\limits_{k=1}^n \mathbb{E} X_i =\sum\limits_{k=1}^n \dfrac{1}{n-d_i}

Fakta ini menunjukkan bahwa kejadian A_\sigma berkardinalitas setidaknya \mathbb{E}X memiliki peluang tak nol. Artinya, haruslah ada suatu himpunan (deterministik) A dengan |A|\geq \mathbb{E}X dan titik-titik di A membentuk subgraf lengkap. Dengan demikian, kita sudah membuktikan klaim kita.

Selanjutnya kita akan menggunakan ketidaksamaan Cauchy-Schwarz sebagai berikut.

\left( \sum\limits_{k=1}^n a_k b_k \right) ^2 \leq \left( \sum\limits_{k=1}^n a_k^2\right) \left( \sum\limits_{k=1}^n b_k^2\right)

Sekarang, kita tetapkan a_k=\sqrt{n-d_k} dan b_k=1/\sqrt{n-d_k}. Kita lihat bahwa ruas kiri menjadi n^2, sementara ruas kanan menjadi

\left(\sum\limits_{k=1}^n (n-d_i)\right) \left(\sum\limits_{k=1}^n \dfrac{1}{n-d_i} \right) \le \omega(G) \left(\sum\limits_{k=1}^n (n-d_i)\right)

Selanjutnya, karena G tidak memiliki K_q sebagai subgraf, maka \omega(G)\le q-1. Selain itu, dengan menggunakan lema jabat tangan (\sum\limits_{k=1}^n d_i=2|E(G)|), kita bisa memperoleh \left(\sum\limits_{k=1}^n (n-d_i)\right) = n^2-2|E(G)|. Dengan demikian, kita mempunyai

n^2 \le (q-1)(n^2-2|E(G)|)

dan ketidaksamaan ini tidak lain adalah pernyataan teorema Turán itu sendiri.

Komentar:

Bagaimana kita dapat mengapresiasi keindahan teorema dan bukti ini? Teorema ini berdasar dari suatu permasalahan yang cukup sederhana untuk dinyatakan (tidak perlu pendefinisian berbagai terminologi yang rumit). Lebih jauh lagi, solusi yang ditawarkan untuk menjadi kandidat struktur ekstrem yang Turán tawarkan begitu naif dan sederhana. Jika Anda mencoba untuk mencari bukti Anda sendiri tanpa mempelajari argumen-argumen di atas, saya cukup yakin Anda akan memikirkan struktur graf Turán dalam percobaan induktif Anda. Namun demikian, kandidat solusi ini sepertinya terlalu naif untuk menjadi struktur ekstrem yang kita cari. Kenyataannya, pembuktiannya memang tidak terlalu straightforward. Hal yang membuatnya makin indah adalah ide liar Spencer dan Alon untuk mengikutsertakan unsur keacakan pada ruang peluang yang tidak terduga, yaitu pemilihan elemen secara uniform acak di ruang permutasi, sesuatu yang sangat tidak natural untuk muncul dalam intuisi matematis orang pada umumnya. Pada kenyataannya, klaim sampingan pada bukti di atas sebetulnya tidak hanya memberi manfaat besar untuk kebutuhan kita. Kita lihat ketika klaim ini kita terapkan pada komplemen graf G, maka kita akan peroleh batas bawah untuk bilangan kebebasan (indepence number) dari suatu graf, yang akan sangat berguna untuk kasus yang lain. Ketidaksamaan ini kemudian dipadukan dengan begitu cerdik dengan ketidaksamaan terkenal Cauchy-Schwarz untuk menghasilkan pintu masuk rahasia kepada Teorema Turán. Pendekatan ini begitu tak terduga dan diatur dengan sangat dramatis untuk memperoleh efek ketakjuban yang sangat memuaskan gairah bermatematika. Itulah sebab bukti ini sangat layak untuk masuk dalam segelintir koleksi bukti matematika terindah sepanjang zaman, sebagaimana Aigner dan Zieglier mengabadikannya dalam museum bukti matematis mahakarya mereka, “Proofs from the Book”.

Advertisements