Combinatorics: Thresholds and Hamming Cubes

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

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.