Combinatorics: Thresholds and Hamming Cubes

New York University, New York NY

Investigators

Abstract

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.