SEMINAR NOTICE
Szemeredi's Regularity Lemma and its applications
Dr. Subrahmanyam Kalyanasundaram, IITH
DATE
& TIME : 12 September
2014,
4.00 PM
VENUE:
Semianr Room, SCIS
Abstract
The Szemeredi's Regularity Lemma states that the vertex set of every large enough graph can be partitioned into equal sized classes so that the edge set across most of the classes looks like a random bipartite graph. This lemma was originally proved by Endre Szemeredi in 1978 in order to help prove a theorem on arithmetic progressions on sets of integers. Despite being originally proven for a specific purpose, it has turned out to be a very powerful and widely used tool in external graph theory. In this talk, we shall state the lemma, sketch the proof and illustrate an application of the lemma.
BIO
Subrahmanyam Kalyanasundaram is an Assistant Professor at Department of Computer Science and Engineering, IIT Hyderabad. He completed his PhD from Georgia Institute of Technology, Atlanta, USA under advisors Richard Lipton and Asaf Shapira. He completed his B Tech from REC (presently NIT) Calicut and completed masters degrees from Indian Institute of Science, Bangalore and Georgia Tech. He is interested in all areas of Theoretical Computer Science.