International Journal of Mathematics and Mathematical Sciences
Volume 13 (1990), Issue 4, Pages 825-827

On the discrepancy of coloring finite sets

D. Hajela

Bellcore, 445 South Street, Morrtstown, New Jersey 07960, USA

Received 11 October 1989

Copyright © 1990 D. Hajela. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.


Given a subset S of {1,,n} and a map X:{1,,n}{1,1}, (i.e. a coloring of {1,,n} with two colors, say red and blue) define the discrepancy of S with respect to X to be dX(S)=|iSX(i)| (the difference between the reds and blues on S). Given n subsets of {1,,n}, a question of Erdos was to find a coloring of {1,,n} which simultaneously minimized the discrepancy of the n subsets. We give new and simple proofs of some of the results obtained previously on this problem via an inequality for vectors.