Probabilistic and Extremal Combinatorics

概率和极值组合学

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

The majority of this research is in the area of probabilistic combinatorics, which is comprised of the study of random combinatorial structures, randomized algorithms and probabilistic existence proofs for combinatorics (i.e. the probabilistic method). In recent years, this field has seen the development of a technique for proving that key statistics of a discrete stochastic process are likely to remain close to their expected trajectories as the process evolves. This method is known as the differential equations method for greedy algorithms and random graph processes. The investigator recently extended this technique to analyze the triangle-free process, a `controlled' random graph process that produces an interesting distribution on the space of triangle-free graphs. The investigator showed that a graph drawn from this distribution is likely to have independence number within a constant multiplicative factor of the smallest possible. In other words, the triangle-free process produces a Ramsey R(3,t) graph. The investigator shall continue the development of this method for the study of related `controlled' random processes, with an emphasis on processes that are interesting from the perspective of extremal combinatorics. Related questions are motivated by computer science. Here the investigator attempts to develop applications of the differential equations method to prove good performance of randomized algorithms without an explicit solution, or numerical approximation of the solution, of the associated differential equation (the need for such information often significantly complicates application of this method).This research project is an investigation of discrete mathematical objects, like networks or codes, whose evolution over time is determined by a sequence of random choices. We are particularly interested in processes where there is dependence between the choices made in different rounds. While such processes can be good models for the dynamics of real-world phenomenon, like the spread of a disease in a network or phase transitions in materials, the focus of this research is on processes that generate interesting mathematical objects. Randomness has long played an important role in the construction of sophisticated combinatorial objects, just as randomness plays an a central role in many algorithms in computer science. This research is expected to have an impact in multiple domains as the investigator shall develop general tools for understanding the evolution of these systems over time.

这项研究的大多数在于概率组合剂的领域，该领域由组合术的随机组合结构，随机组合结构，随机算法和概率存在证明（即概率方法）组成。 近年来，该领域已经看到了一种技术，即证明随着过程的发展，离散随机过程的关键统计数据可能会保持接近其预期的轨迹。 该方法称为贪婪算法和随机图过程的微分方程方法。 研究者最近扩展了该技术以分析无三角形过程，这是一个“受控”随机图过程，在无三角形图的空间上产生有趣的分布。 研究者表明，从该分布中绘制的图可能具有最小可能的恒定乘法因子的独立性数。 换句话说，无三角形的过程产生了Ramsey R（3，T）图。 研究人员应继续开发这种方法，以研究相关的“受控”随机过程，并着重于从极端组合学的角度来看的过程。 相关问题是由计算机科学动机。 Here the investigator attempts to develop applications of the differential equations method to prove good performance of randomized algorithms without an explicit solution, or numerical approximation of the solution, of the associated differential equation (the need for such information often significantly complicates application of this method).This research project is an investigation of discrete mathematical objects, like networks or codes, whose evolution over time is determined by a sequence of random choices. 我们对在不同回合中做出的选择之间存在依赖性的过程特别感兴趣。 尽管这样的过程可能是现实现象动态的良好模型，例如疾病在网络中的传播或材料中的相转换，但这项研究的重点是产生有趣的数学对象的过程。 长期以来，随机性在复杂的组合物体的构建中发挥了重要作用，就像随机性在计算机科学的许多算法中起着核心作用一样。 预计这项研究将对多个领域产生影响，因为研究人员应开发一般的工具来理解这些系统的演变。