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.

该研究项目有两个主要部分。第一个重点是应用微分方程方法分析贪婪算法和随机图过程。 最近的工作的调查员和艾伦弗里兹提供了一种新的技术，采用这种方法来证明良好的性能随机算法的随机图没有显式的解决方案（或数值近似的解决方案）的相关系统的微分方程（需要这样往往复杂的应用程序的方法）。 关键的新思想是使用组合观测来确定常微分方程自治系统中的不变集，通过该方法的标准应用，管理算法的演变。 在这部分的项目中要解决的问题包括稀疏随机图的哈密尔顿性，匹配和3-着色性。 本研究项目的第二部分是由确定图的香农容量的问题。香农容量是图的幂的独立数的函数。 研究者提出了一种新的技术，基于组合稳定性，实现上界的独立数的权力奇循环。这项研究是在概率和极值组合学领域。 概率组合学包括研究随机组合结构，随机算法和组合学的概率存在性证明（即概率方法）。 极值组合学考虑的问题的形式：“多大（或小）可以是一个对象，位于一个特定的离散数学系统，并满足一定的条件？“我们经常关注极端物体的大小的行为，因为底层系统的大小趋于无穷大。 在二十世纪，人们对这两个领域的兴趣广泛增长。 先驱者，如保罗·鄂尔多斯，发现了极值和随机离散结构的许多美丽的性质，在这些领域提出了大量迷人的问题，并设计了强大的方法来解决这些问题，甚至在概率和极值组合学与其他各种领域（包括理论计算机科学，统计物理和信息论）之间的密切联系被发现之前。 图的香农容量是极值组合学和通信理论之间密切相互作用的一个经典例子。 香农容量给出了噪声通信信道的最佳零错误性能的度量，并且在信息论中非常重要。 同时，它也引起了极值组合学中的一些自然问题。