DIMACS TR: 96-10

Szemeredi's Regularity Lemma and its applications in graph theory

Authors: Janos Komlos Miklos Simonovits


Szemer\'edi's Regularity Lemma is an important tool in discrete mathematics. It says that, in some sense, all graphs can be approximated by random-looking graphs. Therefore the lemma helps in proving theorems for arbitrary graphs whenever the corresponding result is easy for random graphs. Recently quite a few new results were obtained by using the Regularity Lemma, and also some new variants and generalizations appeared. In this survey we describe some typical applications and some generalizations.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1996/96-10.ps.gz
DIMACS Home Page