Abstract: Szemeredi's Regularity lemma is key result in extremal graph theory, that roughly states the following: For any $\epsilon>0$, the vertex set of a graph $G=(V,E)$ can be partitioned into $k=C(\epsilon)$ (i.e. a constant number of) parts $V_1, ... , V_k$ of equal size, such that the induced subgraph on most pairs $(V_i, V_j)$ is '$\epsilon$-close' to being a regular bipartite graph. Besides many combinatorial applications, it can also be used to get polynomial time approximation schemes for various problems on dense graphs. We will look at a proof of a weakened version of the Regularity Lemma, and discuss a couple of it's applications.
