Twierdzenie Ramseya dla zbiorów zbiorów

Podczas eksploracji różnych technik dowodzenia dolnych granic dla algorytmów rozproszonych przyszło mi do głowy, że następujący wariant twierdzenia Ramseya może mieć zastosowania - jeśli to prawda.

Podano parametry: $k$ , $K$ , $n$ , a następnie wybrano $N$ aby było wystarczająco duże. Terminologia: podzbiór $m$ jest podzbiorem rozmiaru $m$ .

• Niech = { 1 , 2 , . . . , N } .$A = \{1,2,...,N\}$
• Niech $B$ składa się ze wszystkich $k$ -subsets od $A$ .
• Niech $C$ składa się ze wszystkich $K$ -subsets z $B$ .
• Przypisać farbowanie $f\colon C \to \{0,1\}$ z $C$ .

Teraz Twierdzenie Ramseya (wersja hipergraf) mówi, że bez względu na to, w jaki sposób wybrać $f$ , jest jednobarwny $n$ -subset $B'$ z $B$ : wszystkie $K$ -subsets od $B'$ mają ten sam kolor.

Chciałbym pójść o krok dalej i znaleźć monochromatyczne $n$ -subset $A'$ z $A$ : czy $B' \subset B$ składa się ze wszystkich $k$ -subsets od $A'$ , a następnie wszystkie $K$ -subsets od $B'$ mają ten sam kolor.

Czy to prawda czy fałsz? Czy to ma imię? Czy znasz jakieś referencje?

Jeśli jest to fałsz z jakichś trywialnych powodów, czy istnieje słabszy wariant, który przypomina to twierdzenie?

Zauważył, że pytanie nie jest trywialne tylko wtedy, gdy k, K oba są większe niż 1; dla przypadku k = 1 lub K = 1 jest to zwykłe twierdzenie Ramseya, które jest prawdziwe dla wszystkich n. Musimy też rozpatrywać tylko przypadek > K, w przeciwnym razie twierdzenie jest prawdziwe, ponieważ istnieje co najwyżej jeden podzbiór B 'skonstruowany przez n-podzbiór A' z A.${n \choose k}$${n \choose k}$

Najpierw udowodnimy, że twierdzenie jest fałszywe dla wszystkich k> 1, K> 1 i każde n spełnia > K> .${n \choose k}$$({n-1 \atop k})$

Aby zbudować kontrprzykład, dla dowolnego dużego N i A = [N], musimy skonstruować funkcję barwienia f taką, że dla wszystkich n-podzbiorów A 'z A, jeśli B' składa się ze wszystkich k-podzbiorów A ' , niektóre z K-podzbiorów B 'mają różne kolory. Tutaj mamy następujące spostrzeżenie:

Obserwacja 1. W warunkach, w których k, K> 1 i > K> , dowolny podzbiór B B jest podzbiorem co najwyżej jednego B 'zbudowanego przez n-podzbiór A 'z A.${n \choose k}$$({n-1 \atop k})$

Obserwację można łatwo przedstawić, przedstawiając ją jako hipergraph. Niech A będzie węzłami wykresu G, n-podzbiór A 'z A jest zestawem węzłów pełnego n-podgraphu w G. B' jest zbiorem k-hipersge w całym podgrodzie (2-hipersge jest normal edge) i K-podzbiory B 'to wszystkie kombinacje ( łącznie , gdzie | B '| = ) K . Obserwacja stwierdza: każda k-krotność hiperge w G należy do co najwyżej jednego pełnego pod-wykresu, co jest oczywiste dla > K> , ponieważ dowolne dwa uzupełnione n-podgrafy przecinają co najwyżej n-1 węzłów, z co najwyżej hipergege.$({|B'| \atop K})$${n \choose k}$${n \choose k}$$({n-1 \atop k})$$({n-1 \atop k})$

Następnie możemy przypisać różne kolory w ramach K-podzbiorów C 'konkretnego B' zbudowanego przez n-podzbiór A ', ponieważ żaden element w C' nie pojawi się jako inny K-podzbiór B '' zbudowany przez n-podzestaw ZA''. Dla każdego podzbioru K B, który nie został skonstruowany przez n-podzbiór A, przypisujemy mu losowy kolor. Teraz mamy funkcję kolorowania f, z tą właściwością, że żaden B 'skonstruowany przez n-podzbiór A nie jest monochromatyczny, to znaczy, że niektóre z K-podzbiorów B' mają różne kolory.

Następnie pokazujemy, że twierdzenie jest również fałszywe dla wszystkich k> 1, K> 1 i każde n spełnia > K. Tutaj jedyną różnicą jest n, którą można wybrać tak dużą, że K> nie jest prawdą. Ale przez inną prostą obserwację:${n \choose k}$$({n-1 \atop k})$

Obserwacja 2. Jeżeli część B 'skonstruowana przez n-podzbiór A' z A jest monochromatyczna, wówczas każdy B '' skonstruowany przez n 'podzestaw A' z A 'dla n' <n jest również monochromatyczny.

Możemy więc założyć, że twierdzenie dotyczy większej liczby n, zastosować drugą obserwację i zakończyć sprzeczność w pierwszym przypadku, ustawiając n 'spełnia > K> ; takie n 'musi istnieć przez fakt, że > K i K> , n' musi znajdować się między n a k + 1.$({n' \atop k})$$({n'-1 \atop k})$$({n \atop k})$$({k \atop k})$