Lewati ke konten utama

Subbab 11.5 Teorema Ramsey

Pada tahap ini, Anda mungkin tidak terkejut mengetahui bahwa terdapat bentuk Teorema Ramsey yang sangat umum. Kita mempunyai sejumlah berhingga wadah atau warna dan menempatkan himpunan-himpunan bagian berukuran tetap ke dalam kategori-kategori tersebut. Kesimpulannya ialah bahwa terdapat suatu himpunan besar yang diperlakukan secara seragam.
Berikut pernyataan formalnya.
Kita tidak menyertakan bukti pernyataan umum ini, tetapi mahasiswa yang lebih berambisi dapat mencoba membuktikannya sendiri. Perhatikan bahwa kasus \(s=1\) hanyalah Prinsip Sarang Merpati, sedangkan kasus \(s=r=2\) hanyalah Teorema Ramsey untuk Graf. Bukti untuk kasus umum memerlukan argumen induksi ganda. Induksi pertama dilakukan pada \(r\) dan induksi kedua pada \(s\text{.}\)