Szémeredi's regularity lemma and its applications in combinatorics

Abstract: Szemerédi’s regularity lemma is a deep result in graph theory with applications in many different areas of mathematics. The lemma says that any graph can be approximated by the union of a bounded num- ber of random-like bipartite graphs and this can be used to extract the underlying structure of the graph. Recently it has been shown that there exists polynomial time algorithms that can make this ap- proximation. This survey gives a proof of the regularity lemma, shows some applications and discusses some algorithmic aspects.