Discrepancy of graphs and hypergraphs
Discrepancy of graphs and hypergraphs
-
Alex Scott, Oxford University
Fine Hall 224
How uniformly is it possible to distribute edges in a graph? For instance, is there a graph of density 1/2 in which every induced subgraph has approximately the same number of edges as nonedges? Erdos and Spencer showed in 1971 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} (and gave a similar result for hypergraphs). Erdos, Goldberg, Pach and Spencer subsequently proved a weighted extension of this 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 Bela Bollobas.