Monday, September 9th, 2013 4:00pm-5:00pm Burnside 1205
Department of Mathematics, Oxford University
Discrepancy of graphs and hypergraphs

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.

Fall 2013 Schedule