| Monday, September 9th, 2013 | 4:00pm-5:00pm | Burnside 1205 |
How uniformly is it possible to distribute edges in a graph or hypergraph? This question was asked in 1971 by Erd\H os and Spencer, who defined the {\em discrepancy} of a hypergraph to be the maximum difference between the number of edges and the number of nonedges in any induced subgraph. Erd\H os and Spencer proved that every graph on $n$ vertices has an induced subgraph in which the numbers of edges and nonedges differ by at least cn^{3/2} (which is optimal up to the constant), and gave an extension to hypergraphs. Erd\H os, Goldberg, Pach and Spencer subsequently proved a weighted version for graphs with density p. We shall discuss generalizations of these results and related questions involving intersections of pairs of graphs or hypergraphs. Joint work with B\'ela Bollob\'as.