Bounds on a partition theorem with ambivalent colors 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.
 A: 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.
A: 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 t ∈ Hi. 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.
