## Bounds on a partition theorem with ambivalent colors

### Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

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.

-

## 2 Answers

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.

-

Very nice! After coffee, I got the explicit lower bound $n > \sqrt{2}\exp(3k/40)$ when $h=3$ and $\epsilon=1/4$, by using Bernstein's Inequality instead. – François G. Dorais♦ Mar 25 2010 at 14:15
After more coffee, I successfully generalized your trick to arbitrary h, r; I will post the details separately. Thank you very much for your answer! – François G. Dorais♦ Mar 25 2010 at 14:49
Thx, you're welcome! – domotorp Mar 25 2010 at 16:25

### You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.

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.

-

This answer is community wiki because domtorp deserves all the credit. – François G. Dorais♦ Mar 25 2010 at 16:07
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 3, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 5, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9035097360610962, "perplexity_flag": "middle"}