Erweiterungen von Ramseys Theorem: monochromatisch, aber vielfältig

9

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 m1dknNmm

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

Definitionen:

  • XB ist monochromatisch, wenn für alle Teilmengen und .k S X S 'X.f(S)=f(S)kSXSX
  • XB ist vielfältig, wenn so dass und für alle i .x i < x i + 1 x iX={x1,x2,...,xn}xi<xi+1ixixi+1 mod di

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 XB . Und offensichtlich ist es trivial, eine vielfältige n Teilmenge XB .

Frage: Gibt es immer eine vielfältige und monochromatische n Teilmenge XB ?


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 ndddkn

Jukka Suomela
quelle

Antworten:

7

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,}

  • 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 ) - nnn/dR(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 kn>k+d1dk


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 k1X=x1,,xnS=x1,,xkxixi+1S

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.SSn>k+d+1SXn>dxi,xjjid1n>k+d+1xkXk<ik>jSxineben , das höchstens k-2 mal schaltet. Somit ist eine rote k-Teilmenge.xjS

Hsien-Chih Chang 張顯 之
quelle
1
Ich habe eine Frage zu MO gestellt, um Literatur in verallgemeinerter EHC zu zyklischen Gruppen anzufordern.
Hsien-Chih Chang 15 之
Danke, das war aufschlussreich, aber ich bin nicht sicher, ob es erweitert werden könnte, um zu zeigen, dass die Behauptung für ein zusammengesetztes falsch ist . Wenn zum Beispiel und ungerade ist, kann ein vielfältiges aus Elementen bestehen, die abwechselnd oder mod , und keine Teilmenge ist null mod ? d = 4 k × 1 3 d k ddd=4kX13dkd
Jukka Suomela
In Bezug auf das eigentliche Problem: All dies bezieht sich auf den Nachweis von Aussagen der Form "Es gibt keinen deterministischen verteilten Algorithmus, der dieses Graphproblem in weniger als so vielen Kommunikationsrunden löst". Die Ramsey-Theorie wurde in vielen Fällen erfolgreich angewendet. siehe zB Vorlesung 4 hier . Aber gelegentlich brauche ich etwas Stärkeres als "bloße" monochromatische Teilmengen. Es ist eine lange Geschichte, und an dieser Stelle ist alles peinlich vage, aber wenn dies zu etwas Konkretem führt, werde ich hier sicherlich eine ausführliche Erklärung schreiben!
Jukka Suomela
@Jukka: Danke, dass du uns deine Ideen mitgeteilt hast. Ich hoffe, dass dir bald etwas wirklich Schönes einfällt! Für den Fall, dass d zusammengesetzt ist, habe ich ein paar Ideen, um damit umzugehen, aber es ist immer noch ein wenig chaotisch. Ich werde noch ein paar Stunden nachdenken, bevor ich sie aufschreibe, falls die Ideen nicht auseinanderfallen. ..
Hsien-Chih Chang 15 之
@Jukka: Ich habe einen seltsamen Fehler in meinem Beweis gefunden. In Lemma 3 sollte nicht angenommen werden, dass kleiner als, also kleiner als ? Andernfalls ist es unmöglich, alle zu unterscheiden. Ich werde versuchen, den Fehler zu beheben. Aber derzeit ist der Beweis gebrochen ...| X | d x ik|X|dxi
Hsien-Chih Chang 22 之
6

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.

domotorp
quelle
1
Das ist klug! Und wir brauchen tatsächlich nur . Ihre Antwort schließt fast alle Fälle aus ... Jetzt sind die einzigen Möglichkeiten , die nicht zu viel sind. n ( k - 1 ) dn>(k1)dn(k1)d
Hsien-Chih Chang 24 之