Randomness and Quasi-randomness of Graphs and Set Systems

点击翻译按钮获取中文摘要

Abstract for award of Rodl 0300529The proposed research aims at deepening our understanding ofspontaneous order (studied in Ramsey theory) and of random disorder(investigated by quasi-random techniques). One of its goals is todesign efficient methods for finding and enumerating collections ofspecified sub-objects in discrete structures. The project seeksfurther development of a methodology - the Regularity Method - thathas had a series of striking successes over the past 25 years, and toapply the method to a variety of problems in extremal combinatoricsand Ramsey theory. In the area of quasi-randomness, one of the PI'slong-term projects is to investigate the properties of quasi-randomsparse graphs and uniform hypergraphs. In particular, the PI isinterested in extending the applicability of the Regularity Method tothese structures.The understanding of discrete, combinatorial structures is veryimportant in modern science and technology. For instance,probabilistic reasoning is crucial in the design of large networks andof algorithms. In discrete mathematics, one of the most successfultechniques is the probabilistic method, which enables one to proveresults about deterministic objects. One of the more recenttechniques employs the idea of quasi-randomness. A quasi-randomobject is an object that shares several properties with many otherobjects of the same kind. Quasi-random properties that enable one to find and enumerate sub-objects of a given type are of particularinterest. The main part of this proposal aims to extend theapplicability of the current techniques to a broader class of combinatorialstructures. The results should lead to applications in differentareas, ranging from phase transition and game theory to theoreticalcomputer science.