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.
| 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.