Statistical Methods in Discrete Mathematics

离散数学中的统计方法

• 批准号: 9801396
• 负责人: Janos Komlos
• 金额: $ 18.35万
• 依托单位: Rutgers University New Brunswick
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1998
• 资助国家: 美国
• 起止时间: 1998-06-15 至 2001-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9801396&HistoricalAwards=false
• 关键词: Statistical; Methods; 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.

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