[CSDM] Discrete math seminar

[Paul Seymour]

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


Date: Today, 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)