Combinatorics: Thresholds and Hamming Cubes

组合学：阈值和汉明立方

• 批准号: 2324978
• 负责人: Jinyoung Park
• 金额: $ 17.9万
• 依托单位: New York University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2023
• 资助国家: 美国
• 起止时间: 2023-01-01 至 2025-06-30
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2324978&HistoricalAwards=false
• 关键词: Combinatorics; Thresholds; Hamming; Cubes

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.

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