Searching for (sharp) thresholds in random structures: Where are we now?
Will Perkins · Bulletin of the American Mathematical Society · 2024
We survey the current state of affairs in the study of thresholds and sharp thresholds in random structures on the occasion of the recent proof of the Kahn–Kalai conjecture by Park and Pham and the fairly recent proof of the satisfiability conjecture for large k k by Ding, Sly, and Sun. Random discrete structures appear as fundamental objects of study in many scientific and mathematical fields including statistical physics, combinatorics, algorithms and complexity, social choice theory, coding theory, and statistics. While the models and properties of interest in these fields vary widely, much progress has been made through the development of general tools applicable to large families of models and properties all at once. Historically, these tools originated to solve or make progress on specific difficult conjectures in the areas mentioned above. We will survey recent progress on some of these hard problems and describe some challenges for the future. This survey was prepared in conjunction with a talk for the Current Events Bulletin at the 2024 Joint Mathematics Meetings (JMM) in San Francisco, California.