co.combinatorics - Bounds on a partition theorem with ambivalent colors

Here is a generalization of domotorp's answer to arbitrary h > r > 1.

Independently for each color i ∈ {1,2,...,k}, pick a random H_i 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 = {t₁,...,t_r} iff t ∈ H_i. Let Y_t be the number of 'valid' colors for t. Note that Y_t 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[Y_t ≤ εk] ≤ exp(-2k(p-ε)²)

for 0 < ε < p. So the probability that Y_t ≥ εk for all i is positive whenever n ≤ exp(2k(p-ε)²/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.