Probabilistic and Extremal Combinatorics

概率和极值组合学

• 批准号: 0701183
• 负责人: Tom Bohman
• 金额: $ 13.79万
• 依托单位: Carnegie-Mellon University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2007
• 资助国家: 美国
• 起止时间: 2007-08-01 至 2010-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0701183&HistoricalAwards=false
• 关键词: Probabilistic; Extremal; Combinatorics; Probabilistic; Extremal; Combinatorics

This research project has two main parts. The first focuses on applications of the differential equations method for the analysis of greedy algorithms and random graph processes. Recent work of the investigator and Alan Frieze gives a new technique for employing this method to prove good performance of randomized algorithms on random graphs without an explicit solution (or numerical approximation of the solution) of the associated system of differential equations (the need for such often complicates application of the method). The key new idea is to use combinatorial observations to identify an invariant set in the autonomous system of ordinary differential equations that, by a standard application of the method, governs the evolution of the algorithm. Problems to be addressed in this part of the project include Hamiltonicity, matchings and 3-colorability of sparse random graphs. The second part of this research project is motivated by the problem of determining the Shannon capacities of graphs. The Shannon capacity is a function of the independence numbers of the powers of the graph. The investigator proposes a novel technique, based on combinatorial stability, for attaining upper bounds on the independence numbers of powers of odd cycles. This research is in the areas of probabilistic and extremal combinatorics. Probabilistic combinatorics is comprised of the study of random combinatorial structures, randomized algorithms and probabilistic existence proofs for combinatorics (i.e. the probabilistic method). Extremal combinatorics considers questions of the form: `How large (or small) can an object that lies in a particular discrete mathematical system and satisfies a certain condition be?' We are often concerned with the behavior of the size of the extremal objects as the size of the underlying system goes to infinity. Interest in both fields grew extensively during the twentieth century. Pioneers, such as Paul Erdos, discovered many beautiful properties of extremal and random discrete structures, posed vast arrays of fascinating questions in these areas and devised powerful methods for solving them even before the close connections between probabilistic and extremal combinatorics and various other fields (including theoretical computer science, statistical physics and information theory) were discovered. The Shannon capacities of graphs are a classic example of the close interaction between extremal combinatorics and the theory of communication. The Shannon capacity gives a measure of the optimal zero-error performance of a noisy communication channel and is centrally important in information theory. At the same time, it gives rise to natural questions in extremal combinatorics.

该研究项目有两个主要部分。第一个重点是用于分析贪婪算法和随机图过程的微分方程方法的应用。 研究者和Alan Frieze的最新工作为使用这种方法提供了一种新技术，以证明在随机图上的随机算法表现良好，而无需明确的溶液（或溶液的数值近似）（溶液的数值近似）（对于这种方法通常使该方法的应用通常复杂化的需求））。 关键的新想法是使用组合观测来确定普通微分方程自主系统中设置的不变式，该方程通过该方法的标准应用来控制算法的演变。 该项目的这一部分需要解决的问题包括稀疏随机图的汉密尔顿，匹配和3色。 该研究项目的第二部分是由确定图表的香农能力的问题引起的。香农容量是图形幂的独立数的函数。 研究者提出了一种基于组合稳定性的新技术，以在奇数循环的独立性上获得上限。这项研究在概率和极端组合学领域。 概率组合学是由随机组合结构，随机算法和概率存在证明组合的研究（即概率方法）。 极端组合主义者考虑了形式的问题：“在特定离散的数学系统中可以对象有多大（或小）的大小并满足某种条件？” 我们经常关注极端物体的大小的行为，因为基础系统的大小输入无穷大。 在20世纪，对这两个领域的兴趣都广泛增长。 保罗·埃尔多斯（Paul Erdos）等先驱发现了许多极端和随机离散结构的美丽特性，在这些领域提出了各种各样的迷人问题，并设计了有力的方法，即使在概率和极端组合主义者之间的紧密联系和其他各个领域（包括理论计算机科学，统计物理学和信息理论）之间，也发现了强大的方法来解决它们。 图形的香农能力是极端组合学与交流理论之间紧密相互作用的经典示例。 香农的能力衡量了嘈杂的通信渠道的最佳零错误性能，并且在信息理论中非常重要。 同时，它引起了极端组合学的自然问题。