13
$\begingroup$

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?

$\endgroup$
2
  • 1
    $\begingroup$ 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$. $\endgroup$
    – Lev Reyzin
    Dec 13 '10 at 15:07
  • $\begingroup$ There is now a follow-up question: cstheory.stackexchange.com/questions/3795 $\endgroup$ Dec 14 '10 at 20:57
13
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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$? $\endgroup$ Dec 13 '10 at 18:47
  • $\begingroup$ Yes, it is also false for almost all cases. I'll edit the answer. $\endgroup$ Dec 14 '10 at 0:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.