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

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色性。这个研究项目的第二部分是由确定图的香农能力的问题所激发的。香农容量是图的幂的独立数的函数。提出了一种基于组合稳定性的奇环幂独立数上界求解方法。这项研究是在概率和极值组合学领域。概率组合学是研究随机组合结构、随机算法和组合学的概率存在性证明（即概率方法）的学科。极值组合学考虑这样的问题：“在一个特定的离散数学系统中，满足一定条件的对象能有多大（或多小）？”当底层系统的大小趋于无穷大时，我们经常关注极端对象的大小的行为。在二十世纪，人们对这两个领域的兴趣都得到了广泛的发展。先驱者，如Paul Erdos，发现了极值和随机离散结构的许多美丽特性，在这些领域提出了大量有趣的问题，并设计了强大的方法来解决这些问题，甚至在概率和极值组合学与其他各种领域（包括理论计算机科学、统计物理和信息论）之间的密切联系被发现之前。图的香农能力是极值组合学与通信理论密切联系的一个经典例子。香农容量给出了噪声通信信道的最佳零误差性能的度量，在信息论中是非常重要的。同时，它也引起了极值组合中的一些自然问题。