Bounds on a partition theorem with ambivalent colors - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T12:33:53Z http://mathoverflow.net/feeds/question/19255 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/19255/bounds-on-a-partition-theorem-with-ambivalent-colors Bounds on a partition theorem with ambivalent colors François G. Dorais 2010-03-25T01:04:11Z 2010-03-25T16:29:01Z <p>I've been running into the following type of partition problem.</p> <blockquote> <p>Given positive integers <em>h</em>, <em>r</em>, <em>k</em>, and a real number &epsilon; &isin; (0,1), find <em>n</em> such that if every (unordered) <em>r</em>-tuple from an <em>n</em> element set <em>X</em> is assigned a set of at least &epsilon;<em>k</em> 'valid' colors out of a total of <em>k</em> possible colors, then you can find <em>H</em> &sube; <em>X</em> of size <em>h</em> and a single color which is 'valid' for all <em>r</em>-tuples from <em>H</em>.</p> </blockquote> <p>Lower bounds on the smallest such <em>n</em> can be obtained from lower bounds for Ramsey's Theorem. If <em>k</em> is sufficiently large, then partition the set of colors into [1/&epsilon;] pairwise disjoint sets of approximately equal size to emulate a proper [1/&epsilon;]-coloring of <em>r</em>-tuples. A simple pigeonhole argument shows that this is essentially sharp when <em>r</em> = 1 and <em>k</em> is large enough, i.e. one color must be 'valid' for at least <em>n</em>&epsilon; points.</p> <p>Is the Ramsey bound more or less sharp for <em>r</em> > 1 or are there better lower bounds? The interesting case is when <em>k</em> is large since the proposed Ramsey lower bound is (surprisingly?) independent of <em>k</em>.</p> http://mathoverflow.net/questions/19255/bounds-on-a-partition-theorem-with-ambivalent-colors/19289#19289 Answer by domotorp for Bounds on a partition theorem with ambivalent colors domotorp 2010-03-25T07:47:50Z 2010-03-25T07:47:50Z <p>I do not think that the lower bound could depend only on epsilon. Below is the sketch of my argument.</p> <p>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 <a href="http://en.wikipedia.org/wiki/Hoeffding%2527s_inequality" rel="nofollow">Hoeffding</a> 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.</p> http://mathoverflow.net/questions/19255/bounds-on-a-partition-theorem-with-ambivalent-colors/19322#19322 Answer by François G. Dorais for Bounds on a partition theorem with ambivalent colors François G. Dorais 2010-03-25T16:04:52Z 2010-03-25T16:29:01Z <p>Here is a generalization of domotorp's answer to arbitrary <em>h</em> > <em>r</em> > 1.</p> <p>Independently for each color <em>i</em> &isin; {1,2,...,k}, pick a random <em>H</em><sub><em>i</em></sub> from a family <strong>H</strong> of <em>r</em>-hypergraphs that don't contain any complete <em>r</em>-hypergraph of size <em>h</em>. Declare color <em>i</em> to be 'valid' for the <em>r</em>-tuple <em>t</em> = {<em>t</em><sub>1</sub>,...,<em>t</em><sub><em>r</em></sub>} iff <em>t</em> &isin; <em>H</em><sub><em>i</em></sub>. Let <em>Y</em><sub><em>t</em></sub> be the number of 'valid' colors for <em>t</em>. Note that <em>Y</em><sub><em>t</em></sub> is binomial with parameters (<em>k</em>, p) for some 0 &lt; p &le; 1/2 which is independent of <em>k</em> and also independent of <em>t</em> when <strong>H</strong> is closed under isomorphism. Hoeffding's Inequality then gives</p> <p>Prob[<em>Y</em><sub><em>t</em></sub> &le; &epsilon;k] &le; exp(-2k(p-&epsilon;)<sup>2</sup>)</p> <p>for 0 &lt; &epsilon; &lt; p. So the probability that <em>Y</em><sub><em>t</em></sub> &ge; &epsilon;<em>k</em> for all <em>i</em> is positive whenever <em>n</em> &le; exp(2k(p-&epsilon;)<sup>2</sup>/r) (not optimal). </p> <p>This is not enough since p implicitly depends on <em>n</em>. However, for fixed <em>h</em> > <em>r</em> > 1, p can be bounded away from 0. This can be seen by using for <strong>H</strong> the family of <em>r</em>-partite hypergraphs as domotorp did, but different choices of <strong>H</strong> give better bounds.</p>