Statistical Methods in Discrete Mathematics

Komlos 9801396该奖项支持Komlos和Szmeredi在随机结构理论方面的联合研究。随机结构理论已经很发达了。然而，随机性与离散数学的有趣接口是使用随机或准随机方法来解决确定性问题。PI发展了许多统计方法，包括正则性引理、爆破引理和对图兰定理的某些松弛。它们都是基于某种近似的确定性结构和随机外观的结构。本项目超越了这些工具，并将这些方法扩展到稀疏图和超图。这些方法足够强大，足以帮助解决图和超图理论中的几个经典问题。这项研究属于组合学领域。组合学的目标之一是找到有效的方法来操作和列举离散的对象集合。离散系统的行为对于现代通信来说是极其重要的。例如，大型网络的设计，如那些发生在电话系统中的网络，以及计算机科学中的算法设计，都涉及离散的对象集，这利用了组合研究。

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.