By Serge-Paul Carrasco on May 6, 2022

Solving the Kahn-Kalai Conjecture in Probabilistic Combinatorics

(T) Very simply said, the Kahn-Kalai conjecture explores if a random graph is likely to have some sort of interesting structure such as it will contain a triangle, or it will have a Hamiltonian cycle, e.g. a chain of edges that passes through every vertex exactly once. And, each structure will emerge at a given probability that defines a threshold, the expectation threshold in the conjecture.

Here is the conjecture defined by Professor Kalai:

“Consider a random graph G in G(n,p) and the graph property: G contains a copy of a specific graph H. (Note: H depends on n; a motivating example: H is a Hamiltonian cycle.) Let q be the minimal value for which the expected number of copies of H′ in G is at least 1/2 for every subgraph H′ of H. Let p be the value for which the probability that G contains a copy of H is 1/2.

Conjecture: [Kahn – Kalai 2006] p/q = O(log n)“

Two years ago a group of mathematicians – 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.

Gil Kalai explained in a blog post that proving the full expectation threshold conjecture looked like a difficult task. But it was done in an elegant and short way by Stanford’s Professor Jinyoung Park and PhD student Huy Tuan Pham.

Jinyoung and Huy also used their approach to solve one of Talagrand’s paper conjecture: “On a conjecture of Talagrand on selector processes and a consequence on positive empirical processes“.

Following is the approach described in the excellent article from Quanta Magazine – Elegant Six-Page Proof Reveals the Emergence of Random Structure:

“They thought about the problem in terms of a mathematical object called a cover. A cover is a collection of sets, where every object with a certain property contains one of those sets.

For instance, one possible cover of all Hamiltonian cycles is the collection of all edges. Every Hamiltonian cycle will contain one of those edges.

Park and Pham rewrote the Kahn-Kalai conjecture in a way that let them make use of covers. The original conjecture puts constraints on what the probability of a weighted coin landing on heads should be in order to guarantee that a random graph or set contains some property.

In particular, it says that the probability has to be at least the expectation threshold for the property multiplied by a logarithmic factor.

Park and Pham turned this around: If such a property is not likely to emerge, then the probability assigned to the weighted coin is lower than the expectation threshold multiplied by a logarithmic factor.

That’s where covers come in: When a small cover can be constructed for a subset of structures (like a collection of Hamiltonian cycles), it means that the subset’s contribution to the expectation threshold is small. (Remember that the expectation threshold is calculated by taking a kind of weighted average over all possible structures of a given type.) So what Park and Pham now needed to show was that if a random set is unlikely to contain one target structure, there must exist a small cover for all such target structures. The bulk of their proof was dedicated to constructing that small cover.”

So fun to try to understand very complex maths!

References: