This post describes a totally unexpected breakthrough about expectation and thresholds. The result by Frankston, Kahn, Narayanan, and Park has many startling applications and it builds on the recent breakthrough work of Alweiss, Lovett, Wu and Zhang on the sunflower conjecture. Warm congratulations to Keith, Jeff, Bhargav, and Jinyoung!
Let me mention that important updates on the matter of applying the intermediate value theorem for football (or soccer as referred to in the US) that was discussed in this 2009 post were added to the post. For readers interested in the Google’s quantum supremacy news, here is a link of my main post on the matter.
Thresholds versus fractional expectation-thresholds
This morning the following paper appeared on the arXive: Thresholds versus fractional expectation-thresholds by Keith Frankston, Jeff Kahn, Bhargav Narayanan, and Jinyoung Park.
Abstract: Proving a conjecture of Talagrand, a fractional version of the ‘expectation-threshold’ conjecture of Kalai and the second author, we show for any increasing family F on a finite set X that , where and are the threshold and ‘fractional expectation-threshold’ of F, and ℓ(F) is the largest size of a minimal member of F. This easily implies various heretofore difficult results in probabilistic combinatorics, e.g. thresholds for perfect hypergraph matchings (Johansson-Kahn-Vu) and bounded-degree spanning trees (Montgomery). We also resolve (and vastly extend) one version of the ‘random multi-dimensional assignment’ problem of Frieze and Sorkin. Our approach builds on recent breakthrough work of Alweiss, Lovett, Wu and Zhang on the Erdős-Rado ‘sunflower’ conjecture.
The expectation-threshold conjecture
The 2006 expectation threshold conjecture gives a justification for a naive way to estimate the threshold probability of a random graph property. Suppose that you are asked about the critical probability for a random graph in G(n,p) for having a perfect matching (or a Hamiltonian cycle). You compute the expected number of perfect matchings and realize that when p is C/n this expected number equals 1/2. (For Hamiltonian cycles it will be C’/n.) Of course, if the expectation is one half the probability for a perfect matching can be very low, indeed in this case, an isolated vertex is quite likely but when there is no isolated vertices the expected number of perfect matchings is rather large. Our 2006 conjecture boldly asserts that the gap between the value given by such a naive computation and the true threshold value is at most logarithmic in the number of vertices. Jeff and I tried hard to find a counterexample but instead we managed to find more general and stronger forms of the conjecture that we could not disprove.
Conjectures by Talagrand
The expectation threshold conjecture had some connections with a 1995 paper of Michel Talagrand entitled Are all sets of positive measure essentially convex? In a 2010 STOC paper Are Many Small Sets Explicitly Small? Michel formulated a weaker fractional version of the expectation threshold conjecture which is sufficient for the various applications of the original conjecture. This conjecture (as well as a stronger form also posed by Talagrand) is now verified in the new paper!
Connection to isoperimetry
In our 2006 paper we tried to relate the expectation threshold conjecture to various questions of independent interest related to stability theorems for discrete isoperimetric inequalities. This direction did not play a role in the new paper. Let me note that the isoperimetric problems served as partial motivation for the recent breakthrough results by Peter Keevash, Noam Lifshitz, Eoin Long, and Dor Minzer that are reported in this October 2018 post. See their paper Hypercontractivity for global functions and sharp thresholds.
A sample from the applications
- The threshold value for perfect matching – this was proved already by Erdos and Renyi (1960) and it follow from the new results. The same goes for the threshold for connectivity.
- The threshold value for Hamiltonian circuits – posed as a problem by Erdos and Renyi it was solved by Korshunov (1976) and by Posa (1976).
- The threshold for perfect matching in 3-uniform hypergraphs – was posed by Schmidt and Shamir (1983) and was settled by Johansson, Kahn, and Vu. (It was one of the motivation for my 2006 paper with Jeff.)
- The threshold for bounded degree spanning trees that was open for a long time and was settled by Montgomery (2019).
Let me mention that in various cases the gap between the (fractional) expectation threshold and threshold is a smaller power of log n, or is a constant, or has different behavior. Understanding this through a general theory is still unknown.
Connection to the sunflower breakthrough
What did play a major role in the new development was the recent breakthrough work of Alweiss, Lovett, Wu and Zhang on the Erdős-Rado ‘sunflower’ conjecture. (See this post.) I expected that the method of the sunflower paper will have major applications but this application took me by a surprise.