# 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'$ of $B$: all $K$-subsets of $B'$ have the same colour.

I would like to go one step further and find a monochromatic $n$-subset $A'$ of $A$: if $B' \subset B$ consists of all $k$-subsets of $A'$, then all $K$-subsets of $B'$ 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?

• Not an answer, but a quick reference in case it helps: this seems slightly related to the $(r,s,n)$-covering design problem, where you want (and can get) a small collection of $s$-subsets of $n$ that contains all $r$-subsets of $n$, for $r < s < n$. Dec 13 '10 at 15:07
• There is now a follow-up question: cstheory.stackexchange.com/questions/3795 Dec 14 '10 at 20:57

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'| \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' < 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' \atop k})$ > K > $({n'-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.

• Great, such a simple counterexample, many thanks! I wonder if your idea can be extended to arbitrary $k, K$. For example, is it necessarily false also if $1 \ll k \ll K$ or $1 \ll K \ll k$? Dec 13 '10 at 18:47
• Yes, it is also false for almost all cases. I'll edit the answer. Dec 14 '10 at 0:44