Linear Versus Hereditary Discrepancy

Tom Bohman

Carnegie Mellon

April 17,
refreshments at 3:45pm


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)

Return to seminar home page

Combinatorics Seminar, Mathematics Department, MIT, sara(at-sign)

Page loaded on March 25, 2002 at 09:35 PM. Copyright © 1998-99, Sara C. Billey. All rights reserved.