Cole Franks, Rutgers University

Abstract

The discrepancy of a red-blue coloring of the vertices of a hypergraph is the maximum imbalance between the number of red and blue vertices in any edge. The discrepancy of a hypergraph is the least discrepancy of any red-blue coloring. A major open question is whether the discrepancy of a t-regular hypergraph is O(sqrt{t}). I will discuss some recent joint work with Michael Saks concerning the discrepancy of random regular hypergraphs.