Masalah Cap-Set

07:19:00   Cap Set

Beberapa hari yang lalu, saya diberikan sebuah link oleh Pak Aleams Barra.   Pada link tersebut dijelaskan tentang sebuah masalah Kombinatorika yang baru-baru ini mendapat sebuah perkembangan berarti. Masalah ini biasa disebut sebagai cap set problem.  Masalah ini cukup high-profile karena beberapa matematikawan terkenal seperti Field Medalist Timothy Gowers dan Terrence Tao juga pernah tertarik dalam masalah ini.
Posting Blog Terrence Tao tahun 2007 tentang capset
Posting Blog Timothy Gowers tahun 2011 tentang capset

Dari hasil ini, dua konjektur langsung terbukti (dari post Prof. Gil Kalai) yaitu :

1. Erdos-Szemeredi Sunflower Conjecture dan 
2. Strong Cap Set Conjecture

Teorema 2.8 pada Paper Ini (oleh Noga Alon, Amir Shpilka, and Christopher Umans) 2 menyebabkan 1.  

Yang menghangatkan lagi diskusi tentang cap set baru-baru ini adalah ketika Ernie Croot, Vsevolod F. Lev, dan Péter P. Pach meletakkan paper pra-review mereka ke arxiv.org, tentang progression-free set di $\mathbb{Z}_4^n$ . Teknik Polynomial yang mereka pakai, menjadi game-changing dalam diskusi mengenai cap problem ini, sebelumnya para matematikawan menggunakan pendekatan Metode Fourier untuk memperoleh batas dari cap problem tersebut.  (Péter P. Pach ini ternyata pernah ikut IMO dua kali, dapat medali emas di tahun 2004)

Lemma polynomial (atau sekarang disebut Croot-Lev-Pach Lemma) sebenarnya sudah ditanyakan beberapa kali oleh Vsevolod Lev di mathoverflow (klik disini)  untuk melihat pertanyaaan Vsevolod Lev (dia sudah mencari jawabannya sampai tiga tahun!) (Vsevolod Lev ini ternyata proposer soal IMO 1989 no 6)

Argument yang dipakai oleh Croot-Lev-Pach, di adaptasi oleh matematikawan Jordan Ellenberg dan Dion Gijswijt untuk menyelesaikan masalah cap-set di $\mathbb{F}_q^n$. Setelah melihat Croot-Lev-Pach Lemma,  mereka berdua awalnya membuat paper yang terpisah  (sampai akhirnya mereka sadar bahwa argument mereka mirip) jadi mereka memutuskan untuk (akan) mempublish paper nya sebagai joint paper. (Ternyata si Jordan Ellenberg ini dulu tiga kali ikut IMO, dua kali perfect score 1987/1989 ) (Ternyata juga Dion Gijswijt ini pernah ikut IMO tiga kali, dua kali dapat HM , salah satunya di problem no 6 tahun 1994. )

Yang menarik adalah, argument yang dipakai pada paper diatas, cukup elementer sampai-sampai (seharusnya) mahasiswa matematika S1 bisa mengerti , yang tidak begitu elementer mungkin hanya pembatasan generalized binomial coefficient dengan ketaksamaan probabilistik, tapi jika sudah mengetahui variant-variant dari Ketaksamaan Probabilistic Tchebishev, harusnya tidak masalah.

Pada post-post ini saya akan mencoba (menjelaskan) argumen-argumen yang dipakai pada paper tersebut.   Anda bisa baca paper ini  yang katanya "cukup jelas".   Post-post berikut  ini sebenarnya hanyalah break-down argument dari paper tersebut (karena pak Barra bilang "mulai dari mana?" (breakdown-nya) ).  Saya rasa, yang sudah belajar sedikit tentang vektor space harusnya bisa mengikuti.

Post-post nya saya bagi menjadi 3 bagian: 

1.  Part I  (Ini menjelaskan masalah Cap Set, jika anda baca link di awal post ini, masalahnya dijelaskan oleh sebuah permainan kartu SET , disini saya mencoba menjelaskan mengapa bisa sampai nyasar ke vektor space)

2. Part II (Post ini cukup technical, saya mencoba menjelaskan beberapa pernyataan "satu baris" di paper tersebut yang sebenarnya jika di break-down mungkin 20 baris, tapi tetap elementer)

3. Part III (Karena part II kepanjangan, saya pisah, di Part II key lemma nya yaitu Croot-Lev-Pach Lemma sudah dibuktikan, disini kita pakai argument probabilistik untuk melakukan pembatasan (large deviation problem), saya  tidak buktikan ketaksamaannya karena itu bisa satu paper sendiri (saya paparkan paper nya di post part III )  )

Intinya jika anda mau baca paper nya langsung juga bisa, (cuma tiga halaman).