Batas bawah yang konstruktif pada angka Ramsey
Teorema Ramsey menyatakan itu
Diberikan $s, t\in \mathbb{N}$, ada $n\in \mathbb{N}$ sedemikian rupa sehingga untuk setiap grafik dengan $n$ simpul, itu berisi a $s$-clique atau komplemennya mengandung a $t$-klik.
Terkecil $n$ memuaskan pernyataan itu dilambangkan dengan $R(s, t)$.
Saya menemukan dalam artikel "Metode Probabilistik dalam Kombinatorika, Ceramah oleh Niranjan Balachandran" pernyataan berikut:
Batas bawah konstruktif pada R (s, s), ditemukan oleh Nagy, adalah sebagai berikut: $$R(s, s)\ge \binom{s}{3}$$ (Secara eksplisit, konstruksinya berjalan sebagai berikut: ambil set apa saja $S$, dan putar koleksi semuanya $3$subset elemen dari $S$ menjadi grafik dengan menghubungkan himpunan bagian jika perpotongannya ganjil.)
Saya tidak dapat membuktikan bahwa grafik ini dan pelengkapnya tidak mengandung $s$-cliques. Bantuan apa pun dalam masalah ini akan sangat dihargai.
Jawaban
Mari kita ambil $S = \{1, 2, \dots, s\}$. Apa yang sebenarnya dapat kami tunjukkan adalah grafik Nagy memiliki
- klik berukuran paling banyak $\max\{7, \frac{s-1}{2}\}$, dan
- kumpulan ukuran independen paling banyak $s-1$ atau kurang kapan $s \not\equiv 0 \pmod 4$, dan paling banyak $s$ kapan $s \equiv 0 \pmod 4$.
Ini tidak menunjukkan itu $R(s,s) \ge \binom s3$ untuk semua $s$, tapi itu menunjukkan itu $R(s,s) > \binom s3$, dan bahkan itu $R(\frac{s}{2}, s) > \binom s3$, untuk banyak nilai $s$.
Pertama, mari kita temukan kelompok terbesar. Ada dua kasus:
- Klik tersebut berisi $4$ simpul berpotongan pada elemen yang sama dari $S$: katakan, $\{1,2,3\}$, $\{1,4,5\}$, $\{1,6,7\}$, dan $\{1,8,9\}$. Kemudian setiap simpul lainnya harus mengandung$1$: jika tidak, itu harus memiliki elemen dari masing-masing $\{2,3\}$, $\{4,5\}$, $\{6,7\}$, dan $\{8,9\}$, yang tidak mungkin. Klik seperti itu dapat memiliki paling banyak$\frac{s-1}{2}$ sudut.
- Klik berisi paling banyak $3$ simpul berpotongan pada elemen yang sama dari $S$. Mengatakan$\{1,2,3\}$adalah salah satu simpul. Maka bisa ada paling banyak$2$ simpul lain yang berisi masing-masing $1$, $2$, atau $3$, jadi klik memiliki paling banyak $7$ sudut.
Selanjutnya, mari cari himpunan independen terbesar. Di sini, perhatikan bahwa jika dua simpul dalam himpunan independen berbagi$2$ elemen, dan simpul ketiga di bagian himpunan independen $2$ elemen dengan salah satunya, itu harus berbagi setidaknya satu elemen (dan karenanya $2$elemen) dengan yang lain. Jadi himpunan independen harus terdiri dari cluster, di mana dua simpul dalam sebuah cluster berbagi$2$ elemen, dan dua simpul di luar cluster berbagi $0$.
Sekali lagi, cluster dapat memiliki dua bentuk berbeda:
- Misalkan sebuah cluster memiliki $3$ simpul yang semuanya berbagi sama $2$ elemen: katakan, $\{1,2,3\}$, $\{1,2,4\}$,dan $\{1,2,5\}$. Verteks lain dalam kluster yang hanya berisi satu$\{1,2\}$ harus berisi masing-masing $3$, $4$, dan $5$, yang tidak mungkin. Jadi cluster terdiri dari$k$ simpul dari bentuk $\{1,2,x\}$, yang "habis" $k+2$ elemen dari $S$.
- Misalkan sebuah cluster memiliki paling banyak $2$ simpul berbagi apapun $2$elemen. Lalu jika$\{1,2,3\}$ adalah sebuah simpul di cluster, satu sama lain simpul di cluster harus berisi dua $\{1,2,3\}$, tapi paling banyak bisa ada satu dari setiap jenis, untuk $4$simpul total. Ini harus menggunakan setidaknya$4$ elemen dari $S$, seperti dengan $\{1,2,3\}, \{1,2,4\}, \{1,3,4\}, \{2,3,4\}$.
Kami melihat bahwa cluster menggunakan $k$ elemen dari $S$ dapat berisi paling banyak $k$ simpul, jadi semuanya cluster dapat berisi paling banyak $S$sudut. Tetapi ini hanya mungkin jika semua cluster adalah tipe kedua, dan mencakup semua elemen$S$, yang membutuhkan $s \equiv 0 \pmod 4$.