Abstract
In a recent landmark paper, Park and Pham proved the Kahn-Kalai conjecture. This note provides a simplified version of their proof, replacing the original analytical machinery with a streamlined induction argument. This reduction yields a core proof of just one page and allows for the refinement of the universal constant $K$ to approximately 3.998—likely the optimal value achievable under the current framework. The argument also generalizes to the $\epsilon$-version of the Park-Pham result.
Introduction
In the study of random graphs, such as the Erdős–Rényi model $G(n, p)$, researchers focus heavily on thresholds. A threshold $p_c$ is the probability at which a specific property—such as containing a Hamiltonian cycle—suddenly becomes likely to appear.
A related, more accessible metric is the expectation threshold $q(F)$, which is roughly the probability at which we expect to see at least one instance of the property. While it was long known that $q(F) \leq p_c(F)$, the maximum possible gap between these values was a major mystery in probabilistic combinatorics. In 2007, Jeff Kahn and Gil Kalai conjectured that this gap is at most logarithmic: $p_c(F) \leq K q(F) \log n$.
While Park and Pham settled this conjecture in 2022, their proof involved technical analysis that was difficult to digest. This paper presents a "Book proof"—one so simple and natural that it clarifies the underlying combinatorial structure of the problem.
The Inductive Method
The authors replace the original proof's analytical machinery with a streamlined inductive approach that proceeds on two fronts: the size of the ground set $N$ (e.g., the number of edges in a graph) and the maximum size of the sets in the family $l$ (e.g., the number of edges in a Hamiltonian cycle).
The Truncation Trick
To reduce a large problem to a smaller one, the authors utilize a "truncation" strategy. They select a small subset of elements $W$ from the ground set and analyze what remains of the family $F$ after $W$ is removed.
Double Counting Lemma
The heart of the paper is a combinatorial lemma. Using a double-counting argument, the authors demonstrate that for most choices of $W$, the resulting sub-problem is not "too hard" to solve. This allows the application of the inductive hypothesis. By leveraging the sub-additive nature of the "cost function" (the minimum expectation needed to cover a family), the authors can stitch these sub-problems back together to complete the proof.
Key Insights and Results
Induction is Sufficient
The most significant insight is that the heavy analytical tools used in previous proofs (and related work on the Sunflower Lemma) can be bypassed entirely. A well-constructed inductive setup, supported by averaging arguments to show that "bad" subsets $W$ are rare, is sufficient to prove the conjecture.
Refining the Constant $K$
Because the proof is so direct, the authors can "tune" the parameters—specifically the ratio of elements removed during truncation—to optimize the universal constant $K$. They show that $K \approx 3.998$ is the natural limit of this specific inductive method. For context, previous versions of the proof had constants as high as 8 or were not explicitly optimized.
Generalization to the $\epsilon$-Version
The proof is robust enough to handle the "$\epsilon$-version" of the result, which deals with the probability of the property appearing being $1-\epsilon$ rather than just $1/2$. While the proof for very small $\epsilon$ still relies on a base case established by Bell (2023), the inductive step remains the authors' own.
Conclusion and Future Work
This simplification reduces the core proof of the Covering Theorem—the engine behind the conjecture—to about one page of text. While the authors note that $K \approx 3.998$ is likely a methodological ceiling for this specific framework, the streamlined logic provides a clearer path for applying these results to other threshold problems in computer science and statistical physics.
Summary updated