International Journal of Mathematics and Mathematical Sciences
Volume 13 (1990), Issue 4, Pages 825-827
doi:10.1155/S0161171290001168
On the discrepancy of coloring finite sets
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.
Abstract
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)=|∑i∈SX(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.