Statistical Methods in Discrete Mathematics

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

Komlos 9801396 This award supports joint research of Komlos and Szemeredi in the theory of random structures. The theory of random structures is well developed. The interesting interface of randomness with discrete mathematics, however, is the use of random or quasi-random methods to deterministic problems. The PI's have developed a number of statistical methods, including the Regularity Lemma, the Blow-up Lemma, and certain relaxations of Turan's theorem. They are all based on some kind of approximation of deterministic structures with random-looking ones. The present project goes beyond these tools and extends the methods to sparse graphs and hypergraphs. These methods are strong enough to help attack several hard classical problems in graph and hypergraph theory. This research is in the area of combinatorics. One of the goals of combinatorics is to find efficient methods for manipulating and enumerating discrete collections of objects. The behavior of discrete systems is extremely important to modern communications. For example, the design of large networks, such as those occurring in telephone systems, and the design of algorithms in computer science deal with discrete sets of objects, and this makes use of combinatorial research.