Tata Institute of Fundamental Research

Szemeredi's Regularity Lemma and It's Applications

Student Seminar
Speaker: Rakesh Venkat
Organiser: Shishir Pandey
Date: Friday, 10 Jan 2014, 16:15 to 17:15
Venue: D-405 (D-Block Seminar Room)

(Scan to add to calendar)
Abstract:  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.