Amazing! Keith Frankston, Jeff Kahn, Bhargav Narayanan, Jinyoung Park: Thresholds versus fractional expectation-thresholds

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 p_c(F)=O(q_f(F) \log \ell ({\bf F})), where p_c({\bf F}) and q_f({\bf F}) 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

  1. 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.
  2. The threshold value for Hamiltonian circuits – posed as a problem by  Erdos and Renyi it was solved by Korshunov (1976) and by Posa (1976).
  3. 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.)
  4. 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.

 

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

3 Responses to Amazing! Keith Frankston, Jeff Kahn, Bhargav Narayanan, Jinyoung Park: Thresholds versus fractional expectation-thresholds

  1. Pingback: Gil’s Collegial Quantum Supremacy Skepticism FAQ | Combinatorics and more

  2. Christoph says:

    How are the applications you mention actually derived from this, that is how does one obtain the respective fractional expectation-threshold? One would have to show that some family G (probably the obvious one for each application) w.r.t. which F is weakly p-small actually maximises p. Does this require ad-hoc arguments for each application or is there a more general framework that simplifies this?

    • Gil Kalai says:

      Christoph, try to explore it for the case of triangle matching in 3-uniform hypergraphs. Computing the expectation threshold is very easy and I suppose that adding “fractions” does not make it harder. My memory is that for most cases computing the expectation threshold was a straight-forward computation. (ad-hoc perhaps but very easy.) My guess is that computing fractional expectation-threshold is not harder. We did try at the time to find also examples where computing the expectation threshold is not easy and had a few preliminary candidates. I don’t remember if we had any example where at the end this remained difficult.

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 )

Google photo

You are commenting using your Google 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