Rozszerzenia twierdzenia Ramseya: monochromatyczne, ale różnorodne

Jako kontynuacja mojego poprzedniego pytania , które rozwiązał Hsien-Chih Chang, oto kolejna próba znalezienia odpowiedniego uogólnienia twierdzenia Ramseya. (Nie musisz czytać poprzedniego pytania; ten post jest samodzielny.)

Parametry: podane są liczby całkowite , a następnie jest wybierane jako wystarczająco duże. Terminologia: podzbiór jest podzbiorem rozmiaru .$1 \ll d \ll k \ll n$$N$$m$$m$

Niech . Dla każdego podzbioru przypisz kolor .$B = \{1,2,...,N\}$$k$$S \subset B$$f(S) \in \{0,1\}$

Definicje:

• $X \subset B$ jest monochromatyczne , jeśli dla wszystkich -subsets i .$f(S) = f(S')$$k$$S \subset X$$S' \subset X$
• $X \subset B$ jest zróżnicowany, jeśli taki, że i dla wszystkich i .$X = \{ x_1, x_2, ..., x_n \}$$x_i < x_{i+1}$$x_i\,\not\equiv x_{i+1} \text{ mod } d$$i$

Na przykład, jeśli $d = 10$ , to $\{ 12, 15, 23, 32, 39 \}$ jest zróżnicowane, ale $\{ 12, 15, 25, 32, 39 \}$ nie jest. Należy zauważyć, że podzbiór zróżnicowanego zestawu niekoniecznie jest zróżnicowany.

Teraz Twierdzenie Ramseya mówi, że bez względu na to, w jaki sposób wybrać $f$ , jest jednobarwny $n$ -subset $X \subset B$ . Oczywistym jest, że znalezienie zróżnicowanego $n$ podzbioru X \ podzestaw B jest banalne $X \subset B$.

Pytanie: czy zawsze istnieje zróżnicowany i monochromatyczny $n$ podzestaw $X \subset B$ ?

Edycja: Hsien-Chih Chang pokazuje, że twierdzenie jest fałszywe dla liczby pierwszej , ale co z kompozytem ? W moich aplikacjach będę mieć dużą swobodę w wyborze dokładnych wartości , o ile tylko mogę je dowolnie zwiększyć. Mogą być potęgami liczb pierwszych, iloczynami liczb pierwszych lub czymkolwiek niezbędnym, aby roszczenie było prawdziwe.$d$$d$$d \ll k \ll n$

Najpierw muszę powiedzieć: ten problem jest naprawdę interesujący !! I tutaj krótko opisuję, dlaczego moje poprzednie podejścia zawiodły, jak sugerowano w tym poście o błędnych odpowiedziach.

• Moja pierwsza próba polegała na skonstruowaniu kolorystyki związanej z sumą podzbioru k, która powoduje, że wszystkie podzbiory n nie są monochromatyczne. Lemat 1 jest nadal dostępny; ale Lemma 2 się myliła, obserwując, że jeśli k i d są pokrewnymi liczbami pierwszymi, to n-podzbiór w module d zasugerowany przez @Jukka jest kontrprzykładem.$\{1,3,1,3, \ldots\}$

• Druga próba była dowodem na twierdzenie; licząc stosunek zróżnicowanych i monochromatycznych podzbiorów, mamy nadzieję, że liczba monochromatycznych przewyższy liczbę niezróżnicowanych. Ale jest to błąd w moich obliczeniach, zaobserwowany przez @domotorp: stosunek niezróżnicowania nie zbliży się do zera; zbiega się do około , co jest wyraźnie większe niż .$n$$n/d$$R(n,n;k)^{-n}$

• Trzeci powraca do pierwszej metody i pokazuje, że dla zestawu parametrów słabego ubera ($n > k+d-1$ i $d \mid k$), twierdzenie jest fałszywe. W kombinatorykach addytywnych zastosowaliśmy słynny lemat: twierdzenie EGZ.

Czwarta próba wynika z odpowiedzi @domotorp; jest zarówno sprytny, jak i inspirujący, a ja postaram się zmodyfikować jego dowód, aby poradził sobie ze wszystkimi parametrami. Ale nadal jego metoda jest elegancka i całkowicie doceniam to proste podejście.

Zróżnicowany zestaw n zawiera co najmniej jeden k-podzbiór z co najmniej $k-1$„przełącza między klasami mod”; dokładnie, niech$X = x_1,\ldots,x_n$ bądź zróżnicowanym zestawem n i pozwól $S^* = x_1,\ldots,x_k$, przełącznik jest zdefiniowany, jeśli$x_i$ i $x_{i+1}$są w różnych klasach mod-d. Mamy przełączniki k-1$S^*$.

Niech podzbiór K. $S$być czerwony, jeśli$S$ma co najwyżej przełączniki k-2; w przeciwnym razie jest niebieski . W poprzednim akapicie mieliśmy już niebieski, teraz to udowodniliśmy$n > k+d+1$, jest czerwony $S$ w dowolnym zestawie n $X$. Od$n > d$, są dwie liczby $x_i,x_j$ w tej samej klasie mod-d i $j-i \leq d-1$; i odtąd$n > k+d+1$, jest co najmniej k-2 elementów $x_k$ w $X$ z $k<i$ lub $k>j$. I możemy zbudować podzbiór K.$S$ z $x_i$ obok $x_j$, który przełącza się najwyżej k-2 razy. A zatem$S$ jest czerwonym podzbiorem K.

Mogłem źle zrozumieć twoje pytanie, ale jeśli nie, myślę, że jest ono fałszywe. Pokoloruj k-zestawy, których członkowie są przystające modulo d przez czerwony, pozostałe k-zestawy przez niebieski. Jeśli n> kd, to każdy n-zbiór musi zawierać zestaw k, którego członkowie są przystającymi modułami d, a zatem są czerwone. Z drugiej strony, jeśli zestaw k zawiera dwa kolejne elementy zróżnicowanego zestawu n, wówczas jest niebieski.