Randomness and Quasi-randomness of Graphs and Set Systems

Emory University, Atlanta GA

Investigators

Abstract

Abstract for award of Rodl 0300529 The proposed research aims at deepening our understanding of spontaneous order (studied in Ramsey theory) and of random disorder (investigated by quasi-random techniques). One of its goals is to design efficient methods for finding and enumerating collections of specified sub-objects in discrete structures. The project seeks further development of a methodology - the Regularity Method - that has had a series of striking successes over the past 25 years, and to apply the method to a variety of problems in extremal combinatorics and Ramsey theory. In the area of quasi-randomness, one of the PI's long-term projects is to investigate the properties of quasi-random sparse graphs and uniform hypergraphs. In particular, the PI is interested in extending the applicability of the Regularity Method to these structures. The understanding of discrete, combinatorial structures is very important in modern science and technology. For instance, probabilistic reasoning is crucial in the design of large networks and of algorithms. In discrete mathematics, one of the most successful techniques is the probabilistic method, which enables one to prove results about deterministic objects. One of the more recent techniques employs the idea of quasi-randomness. A quasi-random object is an object that shares several properties with many other objects of the same kind. Quasi-random properties that enable one to find and enumerate sub-objects of a given type are of particular interest. The main part of this proposal aims to extend the applicability of the current techniques to a broader class of combinatorial structures. The results should lead to applications in different areas, ranging from phase transition and game theory to theoretical computer science.