Discrepancy of hypergraphs and geometry
University of Washington
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
Speaker's Contact Info: veszter(at-sign)math.washington.edu
Return to seminar home page
Page loaded on September 25, 2000 at 08:22 PM.
Copyright © 1998-99, Sara C. Billey.
All rights reserved.