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

kahn-kalai

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.

This entry was posted in Combinatorics, Probability and tagged , . Bookmark the permalink.

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

  1. shacharlovett says:

    Really nice proof!

  2. Indeed, a very nice proof!
    Very clever and judicious use of a semi-random approach.
    It’s nice that this works without any heavy machinery.

  3. Douglas Gray says:

    Very inspiring IAS Bio. She started late, had lots of doubts, hats off to her and to Jeff Kahn who believed in her. And now she does this amazing, elegant and clever proof.

  4. Pingback: Aperiodical News Roundup – April 2022 | The Aperiodical

  5. mgflax says:

    Huy Pham gives a whiteboard presentation at https://www.youtube.com/watch?v=ElaaV3OLD9I

  6. Noah Singer says:

    Quick clarification question. When we look at a random graph G and the property “G contains H” for a some fixed H, the original Kahn-Kalai paper (https://arxiv.org/pdf/math/0603218.pdf) gives two different conjectures on expectation thresholds, called there “Conjecture 1” and “Conjecture 2”, where Conjecture 2 concerns the threshold for the event “the expected number of each subgraph H’ of H is at least ½”, while Conjecture 1 also imposes expectation thresholds for every property which “covers” the “contains H” property (not necessarily corresponding to a subgraph).

    Conjecture 1 is weaker than Conjecture 2 and not known to imply it as of [KK’06]. The version of the conjecture given in the Park-Pham paper seems to be Conjecture 1, while the slide in the post seems to be Conjecture 2. Is Conjecture 2 known to be resolved?

    • Gil Kalai says:

      Hi Noah, you are right! Conjecture 1 is vastly more general conjecture of what seems to be a slightly weaker form of Conjecture 2. Conjecture 1 is now been proved, while Conjecture 2 is still open. The Park-Pham proof does not give Conjecture 2 (resolving conjecture 2 is essentially the same as constructing a small cover that is symmetric under vertex permutation, which does not follow from the Park-Pham proof). Conjecture 2 is certainly an interesting remaining question.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s