[CSDM] Discrete math seminar

[Paul Seymour]

                 ***********************************
                 * Princeton Discrete Math Seminar *
                 ***********************************


Date: Thursday February 21st, 4:30 in Fine Hall 224

Speaker: Alex Scott, Oxford

Title: Discrepancy of graphs and hypergraphs

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.


                        -----------

Next week: TBA

Anyone wishing to be added to or removed from this mailing list should
contact Paul Seymour (pds at math.princeton.edu)