Szemeredi's Regularity Lemma
and its applications in graph theory
Authors: Janos Komlos Miklos Simonovits
ABSTRACT
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.
DIMACS Home Page