An official website of the United States government
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 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.
more »
« less
This content will become publicly available on July 1, 2026
A Bayesian Proof of the Spread Lemma
ABSTRACT A key set‐theoretic “spread” lemma has been central to two recent celebrated results in combinatorics: the recent improvements on the sunflower conjecture by Alweiss, Lovett, Wu, and Zhang; and the proof of the fractional Kahn–Kalai conjecture by Frankston, Kahn, Narayanan, and Park. In this work, we present a new proof of the spread lemma, that—perhaps surprisingly—takes advantage of an explicit recasting of the proof in the language of Bayesian inference. We show that from this viewpoint the reasoning proceeds in a straightforward and principled probabilistic manner, leading to a truncated second moment calculation which concludes the proof.
more »
« less
- Award ID(s):
- 2031883
- PAR ID:
- 10636018
- Publisher / Repository:
- Random Structures & Algorithms
- Date Published:
- Journal Name:
- Random Structures & Algorithms
- Volume:
- 66
- Issue:
- 4
- ISSN:
- 1042-9832
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract Szemerédi 's Regularity Lemma is a powerful tool in graph theory. It asserts that all large graphs admit bounded partitions of their edge sets, most classes of which consist of uniformly distributed edges. The original proof of this result was nonconstructive, and a constructive proof was later given by Alon, Duke, Lefmann, Rödl, and Yuster. Szemerédi's Regularity Lemma was extended to hypergraphs by various authors. Frankl and Rödl gave one such extension in the case of 3‐uniform hypergraphs, which was later extended tok‐uniform hypergraphs by Rödl and Skokan. W.T. Gowers gave another such extension, using a different concept of regularity than that of Frankl, Rödl, and Skokan. Here, we give a constructive proof of a regularity lemma for hypergraphs.more » « less
-
Given a fixed graph H, what is the (exponentially small) probability that the number XHof copies of Hin the binomial random graph Gn,pis at least twice its mean? Studied intensively since the mid 1990s, this so‐called infamous upper tail problem remains a challenging testbed for concentration inequalities. In 2011 DeMarco and Kahn formulated an intriguing conjecture about the exponential rate of decay of for fixed ε > 0. We show that this upper tail conjecture is false, by exhibiting an infinite family of graphs violating the conjectured bound.more » « less
-
We propose a variant of the 2-to-1 Games Conjecture that we call the Rich 2-to-1 Games Conjecture and show that it is equivalent to the Unique Games Conjecture. We are motivated by two considerations. Firstly, in light of the recent proof of the 2-to-1 Games Conjecture, we hope to understand how one might make further progress towards a proof of the Unique Games Conjecture. Secondly, the new variant along with perfect completeness in addition, might imply hardness of approximation results that necessarily require perfect completeness and (hence) are not implied by the Unique Games Conjecture.more » « less
