School of Technology and Computer Science Seminars
Szemeredi's Regularity Lemma and It's Applications
by Mr. Rakesh Venkat (School of Technology and Computer Science, TIFR)
Friday, January 10, 2014
from
to
(Asia/Kolkata)
at Colaba Campus ( D-405 (D-Block Seminar Room) )
at Colaba Campus ( D-405 (D-Block Seminar Room) )
Description |
Szemeredi's Regularity lemma is key result in extremal graph theory, that roughly states the following: For any ϵ>0, the vertex set of a graph G=(V,E) can be partitioned into k=C(ϵ) (i.e. a constant number of) parts V1,...,Vk of equal size, such that the induced subgraph on most pairs (Vi,Vj) is 'ϵ-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. |