Amazing: Jinyoung Park and Huy Tuan Pham settled the expectation threshold conjecture!

A brief summary: In the paper, A proof of the Kahn-Kalai conjecture, Jinyoung Park and Huy Tuan Pham proved the 2006 expectation threshold conjecture posed by Jeff Kahn and me. The proof is wonderful. Congratulations Jinyoung and Huy Tuan!

Updates: related articles from Stanford, IAS, and an article by Jordana Cepelewicz on Quanta Magazine.

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 still 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.

Two years ago Keith Frankston, Jeff Kahn, Bhargav Narayanan, and Jinyoung Park proved a weak form of the conjecture which was proposed in a 2010 paper by Michel Talagrand. (See this post.) Indeed, 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 whole array of interesting conjectures and commented that he feels that these conjectures are related to the expectation threshold conjecture to which he offered a weaker fractional version. This weak version suffices for various applications of the original conjecture. Keith, Jeff, Bhargav, and Jinyoung’s work built on the breakthrough work of Alweiss, Lovett, Wu and Zhang on the Erdős-Rado ‘sunflower’ conjecture. 

Proving the full expectation threshold conjecture looked like a  difficult task. The only path that people saw was to try to relate Talagrand’s fractional expectation threshold with our expectation threshold. (Indeed Talagrand also conjectured that they only differ by a multiplicative constant factor. This looked if true very difficult to prove.)  However this is not the path taken by Jinyoung Park and Huy Tuan Pham and they found a direct simple argument! Jinyoung and Huy Tuan also used their method to settle one of the central conjectures (Conj 5.7) from Talagrand’s paper and this will be presented in a forthcoming paper.

The logn gap in our conjecture looked rather narrow but now that it was proved we can ask for conditions that will guarantee a smaller gap. For example, when is the gap only a constant?

Here is a nice IAS video on Jinyoung Park’s path to math.

Here is a lecture by Michel Talagrand.