Statistical Methods in Discrete Mathematics

该奖项支持Komlos和Szemeredi在随机结构理论方面的联合研究。随机结构理论发展得很好。然而，随机与离散数学的有趣接口是使用随机或准随机方法来解决确定性问题。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.