Szemerédi’s Graph Regularity Lemma

Abstract: The method of graph regularity is an important tool in extremal combinatorics, allowing one to obtain good approximations of large graphs if one is willing to put up with terrible constants. Since the method only starts to say something meaningful when the graphs involved are far too large to write down, and since it is somewhat technical by nature, it can be hard to get an intuitive grasp of what the lemma states. In this talk, we’ll attempt to find this intuition anyway and get a big-picture overview of what graph regularity is actually doing, and we’ll see how to apply it to solve specific interesting problems in extremal graph theory.