Szemeredi's Regularity Lemma and Compactness

COMPUTER SCIENCE/DISCRETE MATH II
Topic:Szemeredi's Regularity Lemma and Compactness
Speaker:Balazs Szegedy
Affiliation:IAS
Date:Tuesday, January 17
Time/Room:10:30am - 12:30pm/S-101

We introduce a metric space which is the closure of the isomorphism classes of graphs in a natural topology. It turns out that the regularity lemma is equivalent with the compactness of this space. We present applications, open questions, and relations to other subjects like ergodic theory and extremal combinatorics.