Random graphs and Szemeredi's regularity lemma

Abstract: 

A graph is a kind of discrete structure that encodes connections between objects. The study of large graphs is of broad interest, in fields ranging from number theory to neuroscience. In this talk for a general (mathematical) audience, we first give a brief introduction to the fascinating subject of random graphs. We then discuss Szemeredi's regularity lemma, an important tool in modern graph theory that gives a structural understanding of all large graphs and allows us to use intuition about random graphs in a deterministic setting. We finally present some new theorems about substructures that arise after certain structures are randomly perturbed, and describe how graph regularity can be useful in this area. This is joint work with Benny Sudakov and Michael Krivelevich.