Perluasan teorema Ramsey: monokromatik tetapi beragam

Sebagai tindak lanjut dari pertanyaan saya sebelumnya , yang diselesaikan oleh Hsien-Chih Chang, berikut adalah upaya lain untuk menemukan generalisasi yang sesuai dari teorema Ramsey. (Anda tidak perlu membaca pertanyaan sebelumnya; posting ini mandiri.)

Parameter: bilangan bulat $1 \ll d \ll k \ll n$ diberikan, dan kemudian dipilih menjadi cukup besar. Terminologi: -subset adalah subset dari ukuran .m $N$$m$$m$

Biarkan . Untuk setiap subset , tetapkan warna .k S ⊂ B f ( S ) ∈ { 0 , 1 $B = \{1,2,...,N\}$$k$$S \subset B$$f(S) \in \{0,1\}$

Definisi:

• $X \subset B$ adalah monokromatik jika untuk semua -subsets dan .k S ⊂ X S ′ ⊂ $f(S) = f(S')$$k$$S \subset X$$S' \subset X$
• $X \subset B$ adalah beragam jika sehingga dan untuk semua saya .x i < x i + 1 x $X = \{ x_1, x_2, ..., x_n \}$$x_i < x_{i+1}$$x_i\,\not\equiv x_{i+1} \text{ mod } d$$i$

Misalnya, jika , maka beragam tetapi tidak. Perhatikan bahwa himpunan bagian dari himpunan yang beragam belum tentu beragam.{ 12 , 15 , 23 , 32 , 39 } { 12 , 15 , 25 , 32 , 39 $d = 10$$\{ 12, 15, 23, 32, 39 \}$$\{ 12, 15, 25, 32, 39 \}$

Sekarang teorema Ramsey mengatakan bahwa tidak peduli bagaimana kita memilih , ada monokromatik -subset . Dan jelas itu adalah sepele untuk menemukan beragam -subset .n X ⊂ B n X ⊂ $f$$n$$X \subset B$$n$$X \subset B$

Pertanyaan: apakah ada selalu beragam dan monokromatik -subset ?X ⊂ $n$$X \subset B$

Sunting: Hsien-Chih Chang menunjukkan bahwa klaim tersebut salah untuk perdana , tetapi bagaimana dengan komposit ? Dalam aplikasi saya, saya akan memiliki banyak kebebasan dalam memilih nilai yang tepat dari , selama saya dapat menjadikannya besar secara sewenang-wenang. Mereka bisa menjadi kekuatan bilangan prima, produk dari bilangan prima, atau apa pun yang diperlukan untuk membuat klaim itu benar.d d ≪ k ≪ $d$$d$$d \ll k \ll n$

Pertama-tama saya harus mengatakan: masalah ini sangat menarik !! Dan di sini saya jelaskan secara singkat mengapa pendekatan saya sebelumnya gagal, seperti yang disarankan dalam posting meta ini tentang jawaban yang salah.

• Upaya pertama saya adalah mencoba membangun pewarnaan yang terkait dengan penjumlahan dari himpunan-k yang membuat semua n-himpunan non-monokromatik. Lemma 1 masih tersedia; tetapi Lemma 2 salah, dengan mengamati bahwa jika k dan d adalah prima terkait, maka n-subset dalam modul d yang disarankan oleh @Jukka adalah contoh tandingan.$\{1,3,1,3, \ldots\}$

• Percobaan kedua adalah bukti bagi teorema; dengan menghitung rasio subset yang beragam dan monokromatik , kami berharap bahwa jumlah monokromatik yang akan melampaui yang n -beragam. Tetapi ini adalah kesalahan dalam perhitungan saya, diamati oleh @domotorp: rasio menjadi tidak beragam tidak akan mendekati nol; konvergen sekitar n / d , yang jelas lebih besar dari R ( n , n ; k ) - n .$n$$n/d$$R(n,n;k)^{-n}$

• Yang ketiga kembali ke metode pertama, dan itu menunjukkan bahwa untuk set parameter uber-lemah ( dan ), teorema itu salah. Kami menggunakan lemma terkenal dalam kombinatorik aditif: teorema-EGZ.$n > k+d-1$$d \mid k$

Percobaan keempat adalah karena jawaban oleh @domotorp; itu pintar dan inspiratif, dan saya akan mencoba memodifikasi buktinya untuk menangani semua parameter. Tetapi metodenya tetap elegan, dan saya sangat menghargai pendekatan sederhana ini.

N-set yang beraneka ragam mengandung setidaknya satu k-subset dengan setidaknya "beralih antar kelas mod"; tepatnya, biarkan X = x 1 , ... , x n menjadi n-set beragam, dan biarkan S * = x 1 , ... , x k , sebuah saklar didefinisikan jika x i dan x i + 1 berada di berbagai mod-d kelas. Kami memiliki sakelar k-1 untuk S ∗ .$k-1$$X = x_1,\ldots,x_n$$S^* = x_1,\ldots,x_k$$x_i$$x_{i+1}$$S^*$

Biarkan k-bagian akan merah jika S memiliki paling k-2 switch; kalau tidak biru . Dengan paragraf sebelumnya kita sudah memiliki satu biru, sekarang kita membuktikan bahwa untuk n > k + d + 1 , ada merah S dalam n-set X . Karena n > d , ada dua angka x i , x j dalam kelas mod-d yang sama dan j - i ≤ d - 1 ; dan karena n > k + $S$$S$$n > k+d+1$$S$$X$$n > d$$x_i,x_j$$j-i \leq d-1$ , setidaknya ada k-2 elemen x k di X dengan k < i atau k > j . Dan kita dapat membuat k-subset S dengan x i di sebelah x j , yang hanya berganti paling banyak k-2 kali. Jadi S adalah subset k-merah.$n > k+d+1$$x_k$$X$$k<i$$k>j$$S$$x_i$$x_j$$S$

Saya mungkin salah mengerti pertanyaan Anda, tetapi jika tidak, saya pikir itu salah. Warnai k-set yang anggotanya semuanya kongruen dengan warna merah, k-set lainnya dengan warna biru. Jika n> kd, maka setiap n-set harus mengandung k-set yang anggotanya semuanya modulru d kongruen dan karenanya merah. Di sisi lain, jika k-set berisi dua elemen berturut-turut dari n-set yang beragam, maka itu berwarna biru.