Quasi-randomness and The Regularity Lemma

Emory University, Atlanta GA

Investigators

Abstract

The probabilistic method pioneered and chiefly developed by Paul Erdos has become one of the most powerful tools in combinatorics. Extensive research has been carried out in the study of random graphs and other combinatorial structures, often motivated by applications requiring the proof of existence of certain combinatorial objects. This project is oriented to this vigorously developing area in which probabilistic reasoning plays a crucial role in the proof of deterministic statements. One of the most notable examples is the Regularity Lemma of Szemeredi. This lemma allows one to decompose any graph into components whose quasi-randomness ensures the existence of certain substructures, as though they were random objects. Proof methods based on the Regularity Lemma already have numerous applications in graph theory and theoretical computer science. Recently, some of these techniques have been extended to sparse graphs (to which the original regularity lemma could not be applied) as well as to some set systems. The Principal Investigator plans systematic study of such techniques.