The second Kahn–Kalai conjecture with an edge-count bound

The explanation

Take four points and allow a link between every pair, six possible links in all. Keep each link with probability p, independently, like a biased coin flip. The result is a random graph. Now ask a question: does it contain a perfect matching? That means two links that share no point, so together they touch all four points. Four points allow exactly three such pairs of links. Checking all 64 possible graphs gives the exact answer. The chance of a perfect matching reaches one half at p of about 0.454.

There is a cheap way to guess that number without the full check. Count expected copies of the target and of each of its parts. The expected number of perfect matchings is 3p², and the expected number of single links is 6p. The graph expectation threshold is the smallest p where every part has an expected count of at least one half. Here 3p² equals one half at p of about 0.408, and that is the binding part. The true answer, 0.454, is only about 11 percent higher.

The guess can never be too highSource 1. If the target appears half the time, so does each of its parts. So each part's expected count is at least one half. Jeff Kahn and Gil Kalai conjectured in 2007 that the guess is never far too low eitherSource 2. They allowed a loss of one logarithmic factor, the same for every target graph. A logarithm grows very slowly: log base 2 of a million is about 20. This is the second Kahn–Kalai conjecture.

Some loss is unavoidable. Take a perfect matching on n points, with n large. Expected counts suggest that p near 1/n is enough. The true threshold is near (log n)/nSource 3. The extra factor is needed so that no point is left without links, since a matching must cover every pointSource 4. Round trips through every point, called Hamilton cycles, show the same gapSource 5.

The problem has a sister version. It measures cost with any covering family of small sets, not only copies of the target's own parts. Park and Pham proved that abstract version in 2024Source 6. But its threshold can sit above the graph guess, so it does not settle the graph questionSource 7. In 2025, Dubroff, Kahn and Park reached a loss of the cube of log nSource 8. In 2026, Tran cut the general loss to a squared logarithmSource 9. He also proved the conjecture for trees and some other classesSource 10.

This paper proves the conjecture for every graph with at least one edgeSource 11. The loss is a fixed constant times 1 + log₂ h, where h is the number of links in the target. Since h is less than n², this also gives a constant times log₂ n. The constants are written out, and they do not depend on the targetSource 12. They are very large, about 2048 times e⁵⁰, so the bound is only about how the loss grows.

The obstacle was that losses piled up. Earlier proofs grew the target in stages and paid a logarithmic sampling cost at each stage. Tran suggested a coupling that would pay that cost only onceSource 13. The paper takes a different route. It keeps every possible history of growth steps in one tree. Then it trims every level of the tree with the same random set of linksSource 14. Because the pieces added along any one history never overlap, the reuse stays under control. Only logarithmically many successful rounds are neededSource 15.

Back in the four-point example, the bound is far above 1, so it says nothing there. Its force is for large targets. For a perfect matching on a million points, the target has 500,000 links. Then 1 + log₂ h is about 20. The true threshold is at most a fixed constant times 20 times the cheap guess.

How sure is this? A computer proof checker called Lean has checked formal versions of both bounds. They cover every graph with at least one edge and at most n points, using the actual thresholds. No specialist review of the paper has been published.

What it doesn't show. This does not give the exact threshold, and its constants are far too large for small graphs.