Szemeredi's Regularity Lemma and It's Applications



Friday, 10 January 2014, 16:15 to 17:15


  • D-405 (D-Block Seminar Room)


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.