Combinatorics: Thresholds and Hamming Cubes

该项目侧重于组合学和概率与其他领域的联系的边界问题。该项目的一个主要方向是加深我们对随机离散结构本质的理解。这是概率组合学的核心兴趣，随机离散结构的研究也与其他几个学科密切相关，包括统计物理学和理论计算机科学。近年来，该领域取得了重大进展，PI一直致力于对新工具和技术进行更深入的理解和进一步的开发。该项目还包括与计算机科学密切相关的几个离散结构的经典枚举问题。对这些问题的研究已经发展出许多有趣而美丽的技术，这些技术跨越了数学的界限。该项目关注的问题大致与两个主题有关。第一个主题是随机离散结构的阈值现象。这里的一个大目标是证明Kahn-Kalai猜想，它涉及随机图和相关系统中阈值和期望阈值之间的关系。其他问题大多是关于房产增值门槛的悬而未决的问题。在解决这些问题的过程中，PI的目标是测试这些方法在解决塔拉格兰猜想（Kahn-Kalai猜想的分数版本）时的强度和局限性。第二个主题是Hamming立方体（及相关结构）上的渐近枚举问题，以及立方体上的相关等周问题。各种工具（如图形容器方法，它与聚合物模型和簇展开方法的结合，立方体等周性质的稳定性）有望被开发和改进，以解决这里的问题。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

The project focuses on problems on the borders of combinatorics and probability with connections to other areas. One major direction of the project is to deepen our understanding of the nature of random discrete structures. This is of central interest in probabilistic combinatorics, and the study of random discrete structures is also closely related to several other disciplines, including statistical physics and theoretical computer science. This area has gone through major progress in recent years, and the PI has been working towards a deeper understanding and further development of the new tools and techniques. The project also includes classical enumeration problems on several discrete structures that are closely related to computer science. Studying these problems has been developing lots of interesting and beautiful techniques that cut across mathematical boundaries. The project focuses on problems roughly relating to two topics. The first topic is the threshold phenomena of random discrete structures. A big goal here is to prove the Kahn-Kalai Conjecture, which concerns relationships between thresholds and expectation thresholds in random graphs and related systems. Other problems are mostly open questions about thresholds for increasing properties. In attacking these problems, the PI has been aiming to test the strength and limitations of the methods in the resolution of a conjecture of Talagrand, a fractional version of the Kahn-Kalai Conjecture. The second topic is asymptotic enumeration problems on the Hamming cube (and related structures), and related isoperimetric questions on the cube which are now of independent interest. Various tools (such as the graph container method, its combination with polymer models and cluster expansion method, stability for isoperimetric properties of the cube) are expected to be exploited and improved to solve the problems here.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.