Linear Versus Hereditary Discrepancy*

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