<p>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.</p>

<hr>

<p>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})$.</p>

<p>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:</p>

<blockquote>
  <p><strong>Observation 1.</strong> 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.</p>
</blockquote>

<p>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.</p>

<p>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.</p>

<hr>

<p>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:</p>

<blockquote>
  <p><strong>Observation 2.</strong> 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.</p>
</blockquote>

<p>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.</p>

CC BY-SA 2.5
2010-12-13T18:47:46.213Z
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$?
Jukka Suomela
CC BY-SA 2.5
2010-12-14T00:44:58.100Z
Yes, it is also false for almost all cases. I'll edit the answer.
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2010-12-13T17:55:49.497Z
2010-12-14T03:37:40.437Z
2010-12-14T03:37:40.437Z
Hsien-Chih Chang 張顯之
<p>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.</p>

<hr>

<p>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$.</p>

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

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

<p>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.</p>

<hr>

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

<p>If it is false for some trivial reasons, is there a weaker variant that resembles this claim?</p>

CC BY-SA 2.5
2010-12-13T15:07:30.230Z
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$.
Lev Reyzin
CC BY-SA 2.5
2010-12-14T20:57:05.583Z
There is now a follow-up question: http://cstheory.stackexchange.com/questions/3795
Jukka Suomela
<reference-request><co.combinatorics><ramsey-theory>
Ramsey's theorem for collections of sets
Jukka Suomela
# Ramsey's theorem for collections of sets

(Asked by: username_0 on 2010-12-13)

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?

**Tags:** reference-request, co.combinatorics, ramsey-theory
> **Comments:**
> **username_1**: 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$.  
> **username_0**: There is now a follow-up question: http://cstheory.stackexchange.com/questions/3795  

---

## 1 answers

### Answer by username_2 on 2010-12-13. Score: 13 | Accepted answer

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.

> **Comments:**
> **username_0**: 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$?  
> **username_2**: Yes, it is also false for almost all cases. I'll edit the answer.  

---

