School of Mathematical Sciences

About us menu

Mini-course: Regularity of graphs and hypergraphs

Lecturer: Peter Keevash

Szemerédi’s regularity lemma has impressive applications in many areas of modern graph theory, including extremal graph theory, Ramsey theory and property testing. Roughly speaking, it allows any graph G to be approximated by a weighted graph R, in which the size of R depends only the desired accuracy of approximation, but is independent of the size of G. A key property of this approximation is that it satisfies a ‘counting lemma’, whereby the number of copies of any fixed graph in G can be accurately predicted by the weighted number of copies of this graph in R. An analogous theory for hypergraphs has only been developed quite recently, and its ongoing development is an exciting area of current research.

We will introduce Szmerédi’s regularity lemma and give some of its most famous applications, including the triangle-removal lemma, Roth’s theorem on arithmetic progressions and the linear bound for Ramsey numbers of graphs with bounded maximum degree. Next we will discuss the use of regularity to embed spanning subgraphs of bounded degree via the blow-up lemma of Komlós, Sárközy and Szmerédi. We will conclude with an introduction to hypergraph regularity theory and its applications.

This mini-course is open to anyone interested. A rough guide to the required background is that it will be accessible to PhD students who have some familiarity with graph theory. The lectures will be given in the Mathematics Department of Queen Mary, University of London at 2-4pm on Monday, Tuesday, Thursday and Friday of the week 12-16 April 2010.