Ramseys Theorem für Mengenauflistungen

Während ich verschiedene Techniken zum Nachweis von Untergrenzen für verteilte Algorithmen untersuchte, kam ich zu dem Schluss, dass die folgende Variante von Ramseys Theorem möglicherweise Anwendungen hat - falls dies zufällig zutrifft.

Parameter: $k$ , $K$ , $n$ werden angegeben, und dann wird $N$ ausreichend groß gewählt. Terminologie: Eine $m$ Teilmenge ist eine Teilmenge der Größe $m$ .

• Sei $A = \{1,2,...,N\}$ .
• Lassen allen bestehen -subsets von .k $B$$k$$A$
• Lassen aller bestehen -subsets von B .$C$$K$$B$
• Weisen Sie eine Färbung $f\colon C \to \{0,1\}$ von $C$ .

Nun besagt Ramseys Theorem (die Hypergraph-Version), dass es unabhängig von der Wahl von $f$ eine monochromatische $n$ Teilmenge $B'$ von $B$ : Alle $K$ Teilmengen von $B'$ haben dieselbe Farbe.

Ich möchte noch einen Schritt weiter gehen und eine monochromatische $n$ Teilmenge $A'$ von $A$ : Wenn $B' \subset B$ aus allen $k$ Teilmengen von $A'$ , dann haben alle $K$ Teilmengen von $B'$ die gleiche Farbe.

Ist das wahr oder falsch? Hat es einen Namen? Kennen Sie Referenzen?

Wenn es aus trivialen Gründen falsch ist, gibt es eine schwächere Variante, die dieser Behauptung ähnelt?

Beobachtet, dass die Frage nur dann nicht trivial ist, wenn k, K beide größer als 1 sind; für den Fall k = 1 oder K = 1 ist es nur der normale Ramsey-Satz, der für alle n gilt. Außerdem müssen wir uns nur mit dem Fall befassen, dass > K, sonst ist der Satz wahr, da es höchstens einen (${n \choose k}$ Teilmenge von B ', aufgebaut aus einer n-Teilmenge A' von A.${n \choose k}$

Zunächst beweisen wir, dass der Satz falsch ist für alle k> 1, K> 1 und jedes n erfüllt > K>(n-${n \choose k}$.$({n-1 \atop k})$

Um ein Gegenbeispiel zu konstruieren, müssen wir für jedes große N und A = [N] eine Farbfunktion f so konstruieren, dass für alle n-Teilmengen A 'von A, wenn B' aus allen k-Teilmengen von A 'besteht haben einige der K-Teilmengen von B 'unterschiedliche Farben. Hier haben wir die folgende Beobachtung:

Beobachtung 1. Unter den Bedingungen, dass k, K> 1 und > K>(n-${n \choose k}$ist jede K-Untermenge von B eine Untermenge von höchstens einer B ', die aus einer n-Untermenge A' von A aufgebaut ist.$({n-1 \atop k})$

Die Beobachtung kann leicht durch Darstellung als Hypergraphen erscheinen. Sei A Knoten des Graphen G, eine n-Teilmenge A 'von A ist die Knotenmenge eines vollständigen n-Teilgraphen in G. B' ist die Menge von k-Hyperedges im vollständigen Teilgraphen (ein 2-Hyperedge ist a Normalkante) und K-Teilmengen von B 'sind alle Kombinationen (es gibt insgesamt, wobei | B '| = ($({|B'| \atop K})$ ) von K k -Hyperedgen. Die Beobachtung besagt: Jedes K-Tupel von Hyperedgen in G gehört höchstens zu einem vollständigen n-Subgraphen, was für (${n \choose k}$ > K>(n-${n \choose k}$, da zwei beliebige vollständige n-Teilgraphen höchstens n-1 Knoten mit höchstens(n-1)kreuzen$({n-1 \atop k})$Hyperedges.$({n-1 \atop k})$

Dann können wir innerhalb der K-Teilmengen C 'eines bestimmten B', das aus einer n-Teilmenge A 'besteht, verschiedene Farben zuweisen, da jedes Element in C' nicht als eine andere K-Teilmenge von B '' auftritt, die aus einer n-Teilmenge besteht EIN''. Für jede K-Teilmenge von B, die nicht aus einer n-Teilmenge von A besteht, weisen wir ihr eine zufällige Farbe zu. Nun haben wir eine Färbefunktion f mit der Eigenschaft, dass kein durch n-Teilmenge von A konstruiertes B 'einfarbig ist, das heißt, einige der K-Teilmengen von B' haben unterschiedliche Farben.

Als nächstes zeigen wir, dass der Satz auch für alle k> 1, K> 1 und jedes n falsch ist > K. Hier kann der einzige Unterschied n so groß gewählt werden, dass K>(n-${n \choose k}$ist nicht wahr. Aber durch eine andere einfache Beobachtung:$({n-1 \atop k})$

Beobachtung 2. Wenn ein B ', das aus einer n-Teilmenge A' von A aufgebaut ist, einfarbig ist, dann ist jedes B '', das aus einer n'-Teilmenge A '' von A 'für n' <n aufgebaut ist, auch einfarbig.

Wir können also annehmen, dass der Satz für das größere n gilt, die zweite Beobachtung anwenden und einen Widerspruch zum ersten Fall schließen, indem wir n 'satisfies > K>( n ' -$({n' \atop k})$; ein solches n 'muss durch die Tatsache existieren, dass($({n'-1 \atop k})$> K und K>($({n \atop k})$, n 'muss zwischen n und k + 1 liegen.$({k \atop k})$