Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
add comment

2 Answers

up vote 4 down vote accepted

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.

share|improve this answer
    
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. –  François G. Dorais Mar 25 '10 at 14:15
    
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! –  François G. Dorais Mar 25 '10 at 14:49
    
Thx, you're welcome! –  domotorp Mar 25 '10 at 16:25
add comment

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.

share|improve this answer
    
This answer is community wiki because domtorp deserves all the credit. –  François G. Dorais Mar 25 '10 at 16:07
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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