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 *H* ⊆ *X* 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*.



Bounds on a partition theorem with ambivalent colors
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](http://en.wikipedia.org/wiki/Hoeffding%2527s_inequality) 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.


