Linear Versus Hereditary Discrepancy

ABSTRACT

The concept of hypergraph discrepancy provides a unified combinatorial framework for handling classical discrepancy problems from geometry and number theory. Since the discrepancy of a hypergraph can be small for somewhat arbitrary reasons, variants of hypergraph discrepancy have been introduced in the hopes of getting a better measure of the `intrinsic balance' of a hypergraph. Two such variants are linear discrepancy and hereditary discrepancy. Lov\'asz, Spencer and Vesztergombi proved that the linear discrepancy of a hypergraph $${\mathcal H}$$ is bounded above by the hereditary discrepancy of $${\mathcal H}$$, and conjectured a sharper bound that involves the number of vertices in $${\mathcal H}$$. In this talk 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.

Speaker's Contact Info: tbohman(at-sign)moser.math.cmu.edu