Lovász, Spencer and Vesztergombi proved that the linear discrepancy of a hypergraph
H is bounded above by the hereditary discrepancy of
H, and conjectured a sharper bound that involves the number of vertices in
H. In this paper we give a short proof of this conjecture for hypergraphs of hereditary discrepancy 1. For hypergraphs of higher hereditary discrepancy we give some partial results and propose a sharpening of the conjecture.
Mathematics Subject Classification (2000):
05C65 - 11K38
* A proof of the conjecture of Lovász, Spencer and Vesztergombi for hypergraphs of hereditary discrepancy 1 has also been independently obtained by B. Doerr [6].
Supported in part by NSF grant DMS-0100400.
Research supported by the Technion V. P. R. Fund–M. and M. L. Bank Mathematics Research Fund and by the Fund for the Promotion of Research at the Technion.