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.