Ramsey's theorem for collections of sets While exploring different techniques of proving lower bounds for distributed algorithms, it occurred to me that the following variant of Ramsey's theorem might have applications – if it happens to be true.



Parameters: $k$, $K$, $n$ are given, and then $N$ is chosen to be sufficiently large. Terminology: an $m$-subset is a subset of size $m$.


Let $A = \{1,2,...,N\}$.
Let $B$ consist of all $k$-subsets of $A$.
Let $C$ consist of all $K$-subsets of $B$.
Assign a colouring $f\colon C \to \{0,1\}$ of $C$.


Now Ramsey's theorem (the hypergraph version) says that no matter how we choose $f$, there is a monochromatic $n$-subset $B&#39;$ of $B$: all $K$-subsets of $B&#39;$ have the same colour.

I would like to go one step further and find a monochromatic $n$-subset $A&#39;$ of $A$: if $B&#39; \subset B$ consists of all $k$-subsets of $A&#39;$, then all $K$-subsets of $B&#39;$ have the same colour.



Is this true or false? Does it have a name? Do you happen to know any references?

If it is false for some trivial reasons, is there a weaker variant that resembles this claim?
Observed that the question is non-trivial only when k, K both larger than 1;
for the case k = 1 or K = 1, it is just the normal Ramsey theorem, which is true for all n.
Also, we only have to deal with the case that ${n \choose k}$ > K, otherwise the theorem is true since there is at most one ${n \choose k}$-subset of B' constructed by an n-subset A' of A.



First we prove the theorem is false for all k > 1, K > 1, and any n satisfies ${n \choose k}$ > K > $({n-1 \atop k})$.

In order to construct a counterexample, for any large N and A = [N], we have to construct a coloring function f such that for all n-subset A' of A, if B' consists of all k-subsets of A', some of the K-subsets of B' have different colors. Here we have the following observation:


  Observation 1. Under the conditions that k, K > 1 and ${n \choose k}$ > K > $({n-1 \atop k})$, any K-subset of B is a subset to at most one B' constructed by a n-subset A' of A.


The observation can be easily seem by representing as hypergraphs. Let A be nodes of the graph G, an n-subset A' of A is the node set of a complete n-subgraph in G. B' is the set of k-hyperedges in the complete subgraph (a 2-hyperedge is a normal edge), and K-subsets of B' are the every combinations (there are $({|B&#39;| \atop K})$ in total, where |B'| = ${n \choose k}$) of K k-hyperedges. The observation states: any K-tuple of hyperedges in G belongs to at most one complete n-subgraph, which is obvious for ${n \choose k}$ > K > $({n-1 \atop k})$, since any two complete n-subgraphs intersect at most n-1 nodes, with at most $({n-1 \atop k})$ hyperedges.

Then we can assign different colors within K-subsets C' of a particular B' constructed by a n-subset A', since any element in C' will not occur as another K-subset of B'' constructed by a n-subset A''. For any K-subset of B not constructed by any n-subset of A, we assign random color on it. Now we have a coloring function f, with the property that no B' constructed by n-subset of A is monochromatic, that is, some of the K-subsets of B' have different colors.



Next we show that the theorem is also false for all k > 1, K > 1, and any n satisfies ${n \choose k}$ > K. Here the only difference is n may be chosen so large, that K > $({n-1 \atop k})$ is not true. But by another simple observation:


  Observation 2. If some B' constructed by an n-subset A' of A is monochromatic, then every B'' constructed by an n'-subset A'' of A' for n' &lt; n is also monochromatic.


Hence we can assume the theorem holds on the larger n, apply the second observation, and concludes a contradiction by the first case, by setting n' satisfies $({n&#39; \atop k})$ > K > $({n&#39;-1 \atop k})$; such n' must exist by the fact that $({n \atop k})$ > K and K > $({k \atop k})$, n' must lie between n and k+1.