Randomness and regularity

Abstract

For the last ten years the theory of random structures has been one of the most rapidly evolving fields of discrete mathematics. The existence of sparse structures with good ‘global’ properties has been vital for many applications in mathematics and computer science, and studying properties of such objects led to many challenging mathematical problems. In the paper we report on recent progress on this subject related to some variants of Szemerédi’s Regularity Lemma.