6
$\begingroup$

I've been running into the following type of partition problem.

Given positive integers h, r, k, and a real number ε ∈ (0,1), find n such that if every (unordered) r-tuple from an n element set X is assigned a set of at least εk 'valid' colors out of a total of k possible colors, then you can find HX of size h and a single color which is 'valid' for all r-tuples from H.

Lower bounds on the smallest such n can be obtained from lower bounds for Ramsey's Theorem. If k is sufficiently large, then partition the set of colors into [1/ε] pairwise disjoint sets of approximately equal size to emulate a proper [1/ε]-coloring of r-tuples. A simple pigeonhole argument shows that this is essentially sharp when r = 1 and k is large enough, i.e. one color must be 'valid' for at least nε points.

Is the Ramsey bound more or less sharp for r > 1 or are there better lower bounds? The interesting case is when k is large since the proposed Ramsey lower bound is (surprisingly?) independent of k.

$\endgroup$

2 Answers 2

5
$\begingroup$

I do not think that the lower bound could depend only on epsilon. Below is the sketch of my argument.

Fix h=3, r=2, eps=1/4, thus we color the edges of a graph, each with 25% of all the colors and we are looking for a "monochromatic" triangle. Let us take k random bipartitions of the vertices and color the corresponding edges of the bipartite graph with one color. Using Hoeffding or some similar inequality we get that for big enough k every edge is colored at least k/4 times if n is at most exp(ck), where c is some fixed constant with some positive probability. Therefore the bound must depend on k and not only on epsilon.

$\endgroup$
2
  • $\begingroup$ Very nice! After coffee, I got the explicit lower bound $n > \sqrt{2}\exp(3k/40)$ when $h=3$ and $\epsilon=1/4$, by using Bernstein's Inequality instead. $\endgroup$ Mar 25, 2010 at 14:15
  • $\begingroup$ After more coffee, I successfully generalized your trick to arbitrary h, r; I will post the details separately. Thank you very much for your answer! $\endgroup$ Mar 25, 2010 at 14:49
4
$\begingroup$

Here is a generalization of domotorp's answer to arbitrary h > r > 1.

Independently for each color i ∈ {1,2,...,k}, pick a random Hi from a family H of r-hypergraphs that don't contain any complete r-hypergraph of size h. Declare color i to be 'valid' for the r-tuple t = {t1,...,tr} iff tHi. Let Yt be the number of 'valid' colors for t. Note that Yt is binomial with parameters (k, p) for some 0 < p ≤ 1/2 which is independent of k and also independent of t when H is closed under isomorphism. Hoeffding's Inequality then gives

Prob[Yt ≤ εk] ≤ exp(-2k(p-ε)2)

for 0 < ε < p. So the probability that Yt ≥ εk for all i is positive whenever n ≤ exp(2k(p-ε)2/r) (not optimal).

This is not enough since p implicitly depends on n. However, for fixed h > r > 1, p can be bounded away from 0. This can be seen by using for H the family of r-partite hypergraphs as domotorp did, but different choices of H give better bounds.

$\endgroup$
1
  • $\begingroup$ This answer is community wiki because domtorp deserves all the credit. $\endgroup$ Mar 25, 2010 at 16:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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