Erweiterungen von Ramseys Theorem: monochromatisch, aber vielfältig

Als Folge meiner vorherigen Frage , die von Hsien-Chih Chang gelöst wurde, ist hier ein weiterer Versuch, eine angemessene Verallgemeinerung von Ramseys Theorem zu finden. (Sie müssen die vorherige Frage nicht lesen. Dieser Beitrag ist in sich geschlossen.)

Parameter: Es werden ganze Zahlen angegeben, und dann wird so gewählt, dass es ausreichend groß ist. Terminologie: Eine Teilmenge ist eine Teilmenge der Größe .N m $1 \ll d \ll k \ll n$$N$$m$$m$

Sei . Weisen Sie für jede Teilmenge eine Farbe .k S ≤ B f ( S ) ≤ { 0 , 1 $B = \{1,2,...,N\}$$k$$S \subset B$$f(S) \in \{0,1\}$

Definitionen:

• $X \subset B$ ist monochromatisch, wenn für alle Teilmengen und .k S ≤ X S ' ≤ $f(S) = f(S')$$k$$S \subset X$$S' \subset X$
• $X \subset B$ ist vielfältig, wenn so dass und für alle i .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$

Wenn zum Beispiel $d = 10$ , ist $\{ 12, 15, 23, 32, 39 \}$ vielfältig, $\{ 12, 15, 25, 32, 39 \}$ jedoch nicht. Beachten Sie, dass eine Teilmenge einer vielfältigen Menge nicht unbedingt verschieden ist.

Nun sagt Ramseys Theorem, dass es unabhängig davon, wie wir f wählen $f$, eine monochromatische $n$ Teilmenge $X \subset B$ . Und offensichtlich ist es trivial, eine vielfältige $n$ Teilmenge $X \subset B$ .

Frage: Gibt es immer eine vielfältige und monochromatische $n$ Teilmenge $X \subset B$ ?

Edit: Hsien-Chih Chang zeigt, dass die Behauptung für eine Primzahl falsch ist , aber was ist mit zusammengesetztem ? In meinen Anwendungen habe ich viel Freiheit bei der Auswahl der genauen Werte von , solange ich sie beliebig groß machen kann. Sie können Primzahlen, Produkte von Primzahlen oder was auch immer notwendig sein, um die Behauptung wahr zu machen.d d ≪ k ≪ $d$$d$$d \ll k \ll n$

Zuerst muss ich sagen: Dieses Problem ist wirklich interessant !! Und hier beschreibe ich kurz, warum meine früheren Ansätze fehlgeschlagen sind, wie in diesem Meta-Beitrag über falsche Antworten vorgeschlagen.

• Mein erster Versuch war der Versuch, eine Färbung zu konstruieren, die sich auf die Summenmenge der k-Teilmenge bezieht und alle n-Teilmengen nicht monochromatisch macht. Lemma 1 ist noch verfügbar; aber Lemma 2 war falsch, indem beobachtet wurde, dass, wenn k und d verwandte Primzahlen sind, eine von @Jukka vorgeschlagene n-Teilmenge in Modul d ein Gegenbeispiel ist.$\{1,3,1,3, \ldots\}$

• Der zweite Versuch war ein Beweis für den Satz; Durch Zählen des Verhältnisses von verschiedenen und monochromatischen Teilmengen hoffen wir, dass die Anzahl der monochromatischen Untergruppen die Anzahl der nicht-diversen übersteigt. Aber das ist ein Fehler in meinen Berechnungen, der von @domotorp beobachtet wurde: Das Verhältnis, nicht vielfältig zu sein, nähert sich nicht Null; es konvergiert gegen ungefähr , was deutlich größer als .n / d R ( n , n ; k ) - $n$$n/d$$R(n,n;k)^{-n}$

• Die dritte Methode geht auf die erste Methode zurück und zeigt, dass für einen überschwachen Parametersatz ( und ) der Satz falsch ist. Wir haben ein berühmtes Lemma in der additiven Kombinatorik verwendet: den EGZ-Satz.d ∣ $n > k+d-1$$d \mid k$

Der vierte Versuch ist auf die Antwort von @domotorp zurückzuführen. Es ist sowohl klug als auch inspirierend, und ich werde versuchen, seinen Beweis zu ändern, um mit allen Parametern fertig zu werden. Trotzdem ist seine Methode elegant und ich schätze diesen einfachen Ansatz sehr.

Eine vielfältige n-Menge enthält mindestens eine k-Teilmenge mit mindestens "wechselt zwischen Mod-Klassen"; genau, sei eine vielfältige n-Menge, und sei , ein Schalter ist definiert, wenn und in verschiedenen mod-d sind Klassen. Wir haben k-1 Schalter für .X = x 1 , … , x n S ∗ = x 1 , … , x k x i x i + 1 S $k-1$$X = x_1,\ldots,x_n$$S^* = x_1,\ldots,x_k$$x_i$$x_{i+1}$$S^*$

Eine k-Teilmenge sei rot, wenn höchstens k-2 Schalter hat; sonst ist es blau . Im vorherigen Absatz hatten wir bereits einen blauen, jetzt beweisen wir, dass für in jeder n-Menge ein rotes vorhanden ist . Da , gibt es zwei Zahlen in derselben mod-d-Klasse und ; und da , gibt es mindestens k-2 Elemente in mit oder . Und wir können mit eine k-Teilmenge konstruierenS n > k + d + 1 S X n > d x i , x j j - i ≤ d - 1 n > k + d + 1 x k X k < i k > j S x i x j$S$$S$$n > k+d+1$$S$$X$$n > d$$x_i,x_j$$j-i \leq d-1$$n > k+d+1$$x_k$$X$$k<i$$k>j$$S$$x_i$neben , das höchstens k-2 mal schaltet. Somit ist eine rote k-Teilmenge.$x_j$$S$

Ich hätte Ihre Frage vielleicht falsch verstanden, aber wenn nicht, denke ich, dass sie falsch ist. Färben Sie die k-Sätze, deren Mitglieder alle kongruent sind, mit Rot, die anderen k-Sätze mit Blau. Wenn n> kd ist, muss jede n-Menge eine k-Menge enthalten, deren Mitglieder alle kongruent modulo d sind und daher rot sind. Wenn andererseits eine k-Menge zwei aufeinanderfolgende Elemente einer vielfältigen n-Menge enthält, ist sie blau.