If every point is contained in at most 3 sets and all sets are big, then is the discrepancy zero? - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-20T00:48:03Z http://mathoverflow.net/feeds/question/29096 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/29096/if-every-point-is-contained-in-at-most-3-sets-and-all-sets-are-big-then-is-the-d If every point is contained in at most 3 sets and all sets are big, then is the discrepancy zero? domotorp 2010-06-22T14:39:55Z 2010-06-23T23:37:50Z <p>Suppose we have a finite, 100-uniform system of sets such that any point is contained in at most 3 sets. Is it true that we can color the points such that every set contains 50 red and 50 blue points?</p> <p>The question is by Thomas Rothvoss. A positive answer would solve the <a href="http://www.math.sc.edu/~cooper/combprob.html" rel="nofollow">Three permutations problem of Beck</a>, so a simple answer would be a counterexample...</p> http://mathoverflow.net/questions/29096/if-every-point-is-contained-in-at-most-3-sets-and-all-sets-are-big-then-is-the-d/29294#29294 Answer by Gerry Myerson for If every point is contained in at most 3 sets and all sets are big, then is the discrepancy zero? Gerry Myerson 2010-06-23T23:37:50Z 2010-06-23T23:37:50Z <p>No. </p> <p>Given sets $$a_1,a_2,\dots,a_{99},b_1{\rm\ and\ }a_1,a_2,\dots,a_{99},b_2$$ we see that $b_1$ and $b_2$ must be the same color, say, red. Then from $$b_1,b_2,c_1,c_2,\dots,c_{98}{\rm\ and\ }d_1,d_2,c_1,c_2,\dots,c_{98}$$ we see $d_1$ and $d_2$ must both be red. Then from $$d_1,d_2,e_1,e_2,\dots,e_{98}{\rm\ and\ }f_1,f_2,e_1,e_2,\dots,e_{98}$$ we see that $f_1$ and $f_2$ must both be red. Dot, dot, dot. You wind up with as many elements as you like, all of which must be red, and none of them are in more than two of the sets. Once you have more than 50 of them, you can put them in another set which will then have more than 50 red points. </p> <p>Obviously, we can take 100 to be a variable in this problem and solution, provided we restrict its range to the positive even integers and understand 50 to be 100/2. </p>