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

2010-06-22T14:39:55Z

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...

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?

2010-06-23T23:37:50Z

No.

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.

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.

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

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

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?