CAREER: Threshold Phenomena for Random Discrete Structures and Asymptotic Enumeration Problems

About This Grant

This project explores questions at the intersection of combinatorics and probability, with connections to other fields. A significant focus is on gaining deeper insights into random discrete structures, particularly analyzing the locations of phase transitions (e.g., the molecular changes when water freezes into ice). These are important phenomena in various areas such as statistical physics, theoretical computer science, and network science, as they define the boundary between two phases with distinct properties. Recent advancements in this field have been groundbreaking, and the PI has been committed to advancing the innovative tools developed in recent years. The project will involve both graduate and undergraduate students in research. This project addresses two areas of research. The first focuses on the threshold phenomena of random discrete structures. The primary objectives of the project in this topic are to prove the ``Second" Kahn-Kalai Conjecture, which was the original motivation for the Kahn-Kalai Conjecture, and to prove a conjecture of Talagrand that concerns the suprema of certain classes of stochastic processes. To tackle these challenges, the PI aims to test the strengths and limitations of the methods developed in recent breakthrough results in this field, including some that the PI has contributed to. The second area investigates asymptotic enumeration problems on expander graphs. Various techniques - including entropy methods from information theory, container methods from extremal and probabilistic combinatorics, the cluster expansion method from statistical physics, and isoperimetric inequalities from discrete analysis - are expected to be exploited and improved to tackle 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.