# If every point is contained in at most 3 sets and all sets are big, then is the discrepancy zero?

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?

The question is by Thomas Rothvoss. A positive answer would solve the Three permutations problem of Beck, so a simple answer would be a counterexample...

• I'm sorry, what is a "100-uniform system of sets"? Is that a system of sets, each of which contains exactly 100 elements? If so, why 100? Is the problem trivial for 98 (with each set containing 49 of each color)? Uninteresting for 102? It's certainly false for 2; consider the sets a-b, a-c, b-c, a 2-uniform system such that no point is in more than 3 (or even 2) sets, yet no way to color the points so each set has a red and a blue. – Gerry Myerson Jun 23 '10 at 13:05

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.