Discrepancy of hypergraphs and geometry

Katalin Vesztergombi

University of Washington

October 13,
refreshments at 3:45pm


We color the vertices of a hypergraph with two colors (say red and blue). The discrepancy of this coloring is the maximum of the absolute value of the difference of the red and blue elements for every edge. The discrepancy of the hypergraph is the minimum discrepancy of all two-colorations. The hereditary discrepancy is the maximum discrepancy of all restrictions of the original hypergraph. These notions have connections with many topics in combinatorics and number theory. For example, the hereditary discrepancy is 1 if and only if the incidence matrix of the hypergraph is totally unimodular. One can also give a very nice geometric interpretation of the different discrepancy notions. In spite of deep work by Sos, Beck, Spencer, Matousek and others, many simple questions on discrepancy remain unsolved. For example: how much can the addition of a single new edge increase the hereditary discrepancy? After surveying the basic theory, some partial results on this question will be discussed.

Speaker's Contact Info: veszter(at-sign)math.washington.edu

Return to seminar home page

Combinatorics Seminar, Mathematics Department, MIT, sara(at-sign)math.mit.edu

Page loaded on September 25, 2000 at 08:22 PM. Copyright © 1998-99, Sara C. Billey. All rights reserved.