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


Date: Thursday 10th November, 2.15 in Fine Hall 224
 
Speaker: Jacob Fox, MIT

Title: Graph regularity and removal lemmas

Abstract: Szemeredi's regularity lemma is one of the most powerful tools
in graph theory. It was introduced by Szemeredi in his proof of the
celebrated Erdos-Turan conjecture on long arithmetic progressions in dense
subsets of the integers. Roughly speaking, it says that every large graph
can be partitioned into a small number of parts such that the bipartite
subgraph between almost all pairs of parts is random-like. One of the most
important applications is the graph removal lemma, which roughly says that
every graph with few copies of a fixed graph H can be made H-free by
removing few edges. It remains a significant problem to estimate the bounds
in the regularity lemma and the removal lemma, and their variants. In this
talk I discuss recent joint work with David Conlon which makes progress on
this problem. 

                       -----------

Next week:  Shubhangi Saraf

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