Question

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.

Answer 1

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.

Answer 2

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.