The Probabilistic Method in Combinatorics

组合学中的概率方法

• 批准号: 1700338
• 负责人: Asaf Ferber
• 金额: $ 17万
• 依托单位: Massachusetts Institute of Technology
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2017
• 资助国家: 美国
• 起止时间: 2017-07-01 至 2019-11-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1700338&HistoricalAwards=false
• 关键词: Probabilistic; Method; Combinatorics

This award supports the principal investigator's research on the investigation of the use and applications of the powerful technique known as the probabilistic method, pioneered by Paul Erdos more than sixty years ago. In the last few decades the method has experienced tremendous development, propelled by applications in many areas of science, and in particular in theoretical computer science. The project includes foundational problems in combinatorics where randomization plays a crucial role. Further development of the existing tools as well as invention of new tools and techniques will be used to solve those problems, and to investigate both practical and theoretic applications. Plans to disseminate the new discoveries at major international conferences of experts are included as part of the project.The probabilistic method has become a cornerstone of research in modern combinatorics. This project studies the main open problems and applications, including the Kahn-Kallai conjecture and related problems regarding the threshold behavior of graph properties in random graphs. The aim is to find threshold functions for the appearance of large graphs in a random graph, to prove universality-type results, and to develop general tools for embedding general graphs into arbitrary graphs and digraphs satisfying some given desired pseudorandom properties. Another salient part of the project is the broad topic of packing problems, which concerns partitioning combinatorial objects into members from a specified family of objects. The study of the classical tree-packing conjecture and related problems has led to the development of new embedding techniques which can be useful in different areas and form a central part of the project. The project also considers the broad topic of random sums, which is known as the Littlewood-Offord problem. Motivated by a central problem in the theory of random matrices, resilience-type versions of these question and also working with sums of dependent random variables are considered, with potential impact on error-correcting codes and cryptography.

该奖项支持首席研究员对被称为概率方法的强大技术的使用和应用的调查研究，该方法由Paul Erdos在60多年前开创。在过去的几十年里，该方法经历了巨大的发展，在许多科学领域的应用，特别是在理论计算机科学的推动下。该项目包括组合数学中的基础问题，其中随机化发挥着至关重要的作用。现有工具的进一步发展以及新工具和技术的发明将被用来解决这些问题，并调查实际和理论应用。该计划包括在主要的国际专家会议上传播新发现的计划。概率方法已成为现代组合学研究的基石。本计画研究主要的开放问题与应用，包括Kahn-Kallai猜想与随机图中图性质的门槛行为相关问题。我们的目的是找到阈值功能的出现在一个随机图的大型图，证明普遍性类型的结果，并开发通用工具嵌入一般图到任意图和有向图满足一些给定的期望的伪随机属性。该项目的另一个突出部分是包装问题的广泛主题，它涉及将组合对象划分为指定对象家族的成员。对经典的树填充猜想和相关问题的研究导致了新的嵌入技术的发展，这些技术在不同的领域都很有用，并形成了该项目的核心部分。该项目还考虑了随机和的广泛主题，这被称为Littlewood-Offord问题。受随机矩阵理论中的一个中心问题的启发，考虑了这些问题的连续性类型版本以及相关随机变量的总和，这对纠错码和密码学具有潜在的影响。