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

Given positive integers

h,r,k, and a real number ε ∈ (0,1), findnsuch that if every (unordered)r-tuple from annelement setXis assigned a set of at least εk'valid' colors out of a total ofkpossible colors, then you can findH⊆Xof sizehand a single color which is 'valid' for allr-tuples fromH.

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*.