On the Second Kahn-Kalai Conjecture

Elchanan Mossel, Jonathan Niles-Weed, Nike Sun, Ilias ZadikarXiv 2022 · DOI · arXiv

Abstract

The determination of critical thresholds in random graphs is a central problem in probabilistic combinatorics. While the "first" Kahn–Kalai conjecture regarding general monotone properties was recently resolved, the "second" conjecture, specifically concerning subgraph containment, has remained open. This paper presents a proof of a modified version of the second Kahn–Kalai conjecture. By introducing the "modified subgraph expectation threshold" ($\tilde{p}_E(H)$), the authors demonstrate that the critical threshold $p_c(H)$ is bounded by $\tilde{p}_E(H)$ multiplied by a logarithmic factor. The proof leverages the "Spread Lemma," a powerful technique recently popularized by breakthroughs in the Sunflower Conjecture. Our results confirm that the probability of a graph appearing in a random network is governed by expectation-based values, providing a tighter bound for graph inclusion properties.

Introduction

In the study of random graphs, specifically the Erdős–Rényi model $G(n, p)$, researchers seek to identify the critical threshold $p_c(H)$. This is the smallest edge probability $p$ at which a specific structure $H$ (such as a clique or a Hamiltonian cycle) appears with at least 50% probability. Historically, calculating $p_c(H)$ exactly has proven notoriously difficult. In 2007, Jeff Kahn and Gil Kalai conjectured that this threshold is always within a logarithmic factor of a simpler value called the "expectation threshold" $p_E(H)$.

While the general version of this conjecture (the "first" Kahn–Kalai conjecture) was recently solved in a breakthrough by Frankston, Kahn, Narayanan, and Park, the specific case for subgraph containment—the second Kahn–Kalai conjecture—remained a stubborn open problem. This research bridges that gap by refining the threshold definition and applying modern probabilistic tools.

Methodology: The Modified Subgraph Expectation Threshold

The authors address the gap between expectation and high-probability containment by introducing the modified subgraph expectation threshold, denoted as $\tilde{p}_E(H)$.

Redefining the Threshold

Standard expectation thresholds $p_E(H)$ look for the probability where one expects to see at least one copy of every subgraph $H' \subseteq H$. The authors' modified version, $\tilde{p}_E(H)$, requires that we expect to see a large number of copies—specifically, at least half as many as the total number of copies $H$ contains. This tighter requirement allows the threshold to interact more effectively with modern analytical techniques.

The Spread Lemma

The core of the proof relies on the "Spread Lemma." This technique has recently revolutionized combinatorics, leading to the solution of the Sunflower Conjecture. It provides a method to prove that a random set contains a specific structure if the distribution of that structure is sufficiently "spread out"—meaning no small set of elements is overly likely to be part of the structure. The authors prove that their new threshold $\tilde{p}_E(H)$ is "sandwiched" between the original expectation threshold and the true critical threshold, allowing them to apply the Spread Lemma to bound $p_c(H)$.

Key Insights and Results

The research yields several critical insights into the nature of random graphs:

  • The "Many Copies" Intuition: The fundamental observation is that if a random graph contains a copy of $H$, and $H$ is dense with copies of a smaller subgraph $H'$, then the random graph must also contain many copies of $H'$. This intuition allows for a more robust threshold definition.
  • Refining Fractional Covers: The authors show that their result improves upon the "fractional" version of the Kahn–Kalai conjecture for graph inclusion properties, providing an explicit choice of fractional covers that makes the mathematical framework more concrete.
  • Universality of the Logarithmic Factor: The paper reinforces why the $\log e(H)$ factor (where $e(H)$ is the number of edges) is necessary. For structures like Hamiltonian cycles, the expectation threshold is roughly $1/n$, but the actual threshold requires an extra $\log n$ factor to avoid isolated vertices that prevent cycle formation.

Main Theorem

The primary result is Theorem 1, which proves that $p_c(H) \leq L \cdot \tilde{p}_E(H) \log e(H)$ for some universal constant $L$. This confirms a version of the second Kahn–Kalai conjecture using the modified threshold. The authors demonstrate that for important cases like Hamiltonian cycles, their modified threshold behaves correctly, showing that the logarithmic bound is tight.

Conclusion and Future Work

This work demonstrates that the "spread" property is the correct lens through which to view threshold phenomena in random graphs. While the paper proves the conjecture for the modified threshold $\tilde{p}_E(H)$, it remains an open question whether the original, simpler expectation threshold $p_E(H)$ proposed by Kahn and Kalai also satisfies the same bound. The lineage of this research, drawing from the foundations of Erdős, Rényi, and the recent breakthroughs in the Sunflower Lemma, provides a clear path for future investigations into probabilistic combinatorics.

Selected references highlighting the foundational works in random graph theory and threshold conjectures.

Summary updated

Abstract

For any given graph $H$, we are interested in $p_\mathrm{crit}(H)$, the minimal $p$ such that the Erdős-Rényi graph $G(n,p)$ contains a copy of $H$ with probability at least $1/2$. Kahn and Kalai (2007) conjectured that $p_\mathrm{crit}(H)$ is given up to a logarithmic factor by a simpler "subgraph expectation threshold" $p_\mathrm{E}(H)$, which is the minimal $p$ such that for every subgraph $H'\subseteq H$, the Erdős-Rényi graph $G(n,p)$ contains \emph{in expectation} at least $1/2$ copies of $H'$. It is trivial that $p_\mathrm{E}(H) \le p_\mathrm{crit}(H)$, and the so-called "second Kahn-Kalai conjecture" states that $p_\mathrm{crit}(H) \lesssim p_\mathrm{E}(H) \log e(H)$ where $e(H)$ is the number of edges in $H$. In this article, we present a natural modification $p_\mathrm{E, new}(H)$ of the Kahn--Kalai subgraph expectation threshold, which we show is sandwiched between $p_\mathrm{E}(H)$ and $p_\mathrm{crit}(H)$. The new definition $p_\mathrm{E, new}(H)$ is based on the simple observation that if $G(n,p)$ contains a copy of $H$ and $H$ contains \emph{many} copies of $H'$, then $G(n,p)$ must also contain \emph{many} copies of $H'$. We then show that $p_\mathrm{crit}(H) \lesssim p_\mathrm{E, new}(H) \log e(H)$, thus proving a modification of the second Kahn--Kalai conjecture. The bound follows by a direct application of the set-theoretic "spread" property, which led to recent breakthroughs in the sunflower conjecture by Alweiss, Lovett, Wu and Zhang and the first fractional Kahn--Kalai conjecture by Frankston, Kahn, Narayanan and Park.
BibTeX
@misc{mossel2022second,
  author = {Elchanan Mossel and Jonathan Niles-Weed and Nike Sun and Ilias Zadik},
  title = {{On the Second Kahn-Kalai Conjecture}},
  year = {2022},
  eprint = {2209.03326},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2209.03326},
}
Figure