Linear Versus Hereditary Discrepancy
Tom Bohman
Carnegie Mellon
April 17,
4:15pm
refreshments at 3:45pm
2338
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(atsign)moser.math.cmu.edu
Return to seminar home page
Page loaded on March 25, 2002 at 09:35 PM.

Copyright © 199899, Sara C. Billey.
All rights reserved.

