Episode 176, October 2026

Kahn–Kalai, the second one?

A preprint claims that a graph appears in a random graph once every piece of it is expected, up to a fixed constant and the logarithm of its number of edges

Covers result 176 in OpenAI’s catalog: its one paper. See its connections to other results and the work it cites.

Play Episode 176: Kahn–Kalai, the second one? A random graph on eleven dots with one copy of a small graph highlighted in pink (our drawing).

5:37. English captions available. The video loads from YouTube when you press play.

Chapters

The claim, in plain words

In the random graph G(n,p), each pair of n dots is joined independently with probability p. For a fixed graph H, the threshold p_c(n,H) is the p at which a copy of H appears with probability one half. There is an obvious lower bound: at the threshold H appears half the time, and so does every subgraph F of H, so every F must have an expected number of copies of at least one half. The least p where that holds for every F is the graph expectation threshold p_E(n,H), counting ordinary (unlabelled) copies, and always p_E ≤ p_c. For a triangle on six dots, p_E ≈ 0.29 and p_c ≈ 0.36 (our exact computation). The two can drift apart: for a perfect matching on n dots, p_E is about e/n, but a perfect matching needs every dot to have an edge, which takes about (ln n)/n; at a million dots that is about 5 times higher (our computation). Kahn and Kalai conjectured in 2007 that p_c is always at most p_E times a logarithmic factor. As the paper recounts, their abstract conjecture with covers was proved by Frankston, Kahn, Narayanan and Park (fractional form) and by Park and Pham, but for graphs the cover threshold is at least p_E and possibly larger, so the abstract theorem alone did not settle the graph version; Mossel, Niles-Weed, Sun and Zadik proved a single logarithm for a modified threshold, Dubroff, Kahn and Park reached log³ n, and a preprint by Tran, in a version dated the same day as this paper, reached the square of a logarithm and settled trees and some other classes.

Result 176 is one OpenAI preprint, The second Kahn–Kalai conjecture (12 pages, dated September 24, 2026). Its Theorem 1.1: for every n ≥ 2 and every graph H with h ≥ 1 edges and at most n vertices, p_c(n,H) ≤ min{1, 2048 e⁵⁰ p_E(n,H)(1 + log₂ h)}. The constant is explicit and universal, and H may grow with n, so spanning graphs such as perfect matchings are included. In particular, p_c(n,H) ≤ 6144 e⁵⁰ p_E(n,H) log₂ n.

What it doesn’t claim

No small constant. 2048 e⁵⁰ is about 1.06 × 10²⁵, so the bound says something only when p_E(1 + log₂ h) is below about 10⁻²⁵; for perfect matchings, by our computation, only beyond about 2.6 × 10²⁷ dots. It locates no threshold exactly, and it does not say the logarithm is needed for every graph. The counting convention matters: with labelled copies instead of ordinary ones, a perfect matching’s expectation threshold at a million dots would be smaller by a factor of about 370,000 (our computation). That factor grows like n, so for large enough n the statement would be false: by our computation the bound would fall below the no-isolated-dot threshold, a lower bound for p_c, beyond about 1.1 × 10²⁶ dots. The paper cites result 175’s comparison of expectation thresholds only as context; “the proof below does not use it.”

Where it stands

Posted as a preprint: OpenAI, 12 pages, dated September 24, 2026
Peer reviewed: Not yet
Checked in Lean: Formalized by OpenAI with the same explicit constants; not run by us

Last checked October 19, 2026. The preprint has not been revised since it was added to the repository in its initial commit on October 6, 2026. OpenAI published a Lean formalization whose comparator statement states Theorem 1.1 with the same explicit constants, counting ordinary copies. By our count the proof takes 37 files and 6,753 lines, excluding Mathlib (source), with no unproved steps by our search; we have not rebuilt it. The paper is not among those OSVerify reviewed, and we have seen no expert review.

How the proof goes

A spread hierarchy. Following a construction of Tran, the proof peels H into a chain of subgraphs from the empty graph to H, in which each step adds at least 16 times as many new edges as the step before. The steps are spread: no particular set J of new edges is likelier than (128 p_E)^|J|.
A tree of copies. All the ways of extending a copy of one stage to the next form a tree. Each path from the root spells out a copy of H, and along a path the new edges never overlap.
Bayesian resampling. A trick of Mossel, Niles-Weed, Sun and Zadik: pick a random next step (one step’s new edges), add a random set of edges W, and resample a step from the posterior given the union. The part of the new step outside W is the leftover, and with high probability it is at most half as big.
One W for the whole tree. The paper’s move is to do this at every node with the same W. Sharing W creates dependence, but disjointness along paths keeps it under control, and a potential function shows that the whole tree shrinks with probability at least 3/4.
Iteration. After about log₂ h successful rounds every leftover is empty. The random sets, failed rounds included, form one random graph of density at most 2048 e⁵⁰ p_E(1 + log₂ h), which contains a copy of H with probability at least 2/3.

The numbers in the video

Our exact computation of p_c and p_E for small graphs on six dots, by enumerating all 2¹⁵ graphs: a triangle has p_E = 0.292402 and p_c = 0.355724.
Perfect matchings: n p_E tends to e, while the threshold for having no isolated dot grows like ln n (our computation, from 10 to 10⁹ dots).
The labelled-copies comparison at a million dots: p_E = 2.72 × 10⁻⁶ with ordinary copies and 7.39 × 10⁻¹² with labelled copies; the threshold is at least about 1.42 × 10⁻⁵, the no-isolated-dot threshold (our computation). With labelled copies the bound would fail beyond about 1.1 × 10²⁶ dots (our computation).
The constants: 2048 e⁵⁰ ≈ 1.06 × 10²⁵ and 6144 e⁵⁰ ≈ 3.19 × 10²⁵; for perfect matchings the bound first drops below 1 at about 2.6 × 10²⁷ dots (our computation).
The Lean count: our count of the import closure.

Read the source

The second Kahn–Kalai conjecture (PDF), 12 pages.
The Lean scope note.
The collection’s catalog, where this is result 176.

The paper

OpenAI groups related papers into one result; this one has a single paper.

The second Kahn–Kalai conjecture

Transcript

Read the full script

0:00The question

Throw down edges at random: between every pair of n dots, an edge, independently, with probability p. When does a fixed graph H, like a triangle, appear? Its threshold is the p at which the chance of seeing a copy reaches 1/2. There is an obvious lower bound. At the threshold, H is there half the time, so every piece of it is too, and so every subgraph of H must have an expected count of at least 1/2. The smallest p where that holds for all subgraphs at once is the graph expectation threshold, p_E, counting ordinary copies, without labels. On 6 dots, a triangle has p_E of about 0.29 and a threshold of about 0.36. The two can drift apart. For a perfect matching on n dots, p_E is about e/n. But a perfect matching needs every dot to have an edge, which takes about the log of n, over n. In our computation for a million dots, that is about 5 times higher. In 2007, Kahn and Kalai conjectured that this obvious obstruction decides the threshold up to a logarithmic factor, for every graph. They also made an abstract conjecture, for any increasing property, with an expectation threshold defined by covers. Frankston, Kahn, Narayanan and Park proved a fractional form of it, and Park and Pham proved it in full. But for graphs, the cover threshold is at least p_E and possibly larger, so the abstract theorem alone did not settle the graph version. Mossel, Niles-Weed, Sun and Zadik proved a single logarithm for a modified threshold. Dubroff, Kahn and Park reached the cube of the log of n. And a preprint by Tran, in a version dated the same day as this paper, reached the square of a logarithm and settled trees and some other classes.

1:50The claim

Result 176 is a single OpenAI preprint, 12 pages long, dated September 24, 2026. Its theorem: for every n of at least 2, and every graph H with h edges, at least one, and at most n vertices, the threshold is at most 2048 e⁵⁰, times p_E, times one plus the base-two log of h. The constant is explicit and universal, and H may grow with n, so spanning graphs like perfect matchings are included. In particular, the threshold is at most 6144 e⁵⁰, times p_E, times the base-two log of n. Not claimed: a small constant. 2048 e⁵⁰ is about 10²⁵, so the bound says something only when p_E times the log factor is below about 10⁻²⁵; for perfect matchings, by our computation, only beyond about 2.6 × 10²⁷ dots. It locates no threshold exactly, and does not say the log is needed for every graph. The counting convention matters: with labelled copies instead of ordinary ones, the perfect matching’s expectation threshold would be smaller by a factor of about 370,000 at a million dots. That factor grows like n, so for large enough n the statement would be false. The paper cites result 175’s comparison of expectation thresholds only as context; its proof does not use it.

3:25How the proof goes

The proof plants H in stages. Following a construction of Tran, it peels H into a chain of subgraphs, from empty to all of H, in which each step adds at least 16 times as many new edges as the step before. The steps are chosen to be spread: no particular set of new edges is likelier than 128 p_E, to the power of its size. All the ways of extending a copy of one stage to the next form a tree. Each path from the root spells out a copy of H, and along any path the new edges never overlap. Then comes a Bayesian trick of Mossel, Niles-Weed, Sun and Zadik. Pick a random next step, add a random set of edges W, and resample a step from the posterior, given the union. The part of the new step outside W is the leftover, and with high probability it is at most half as big. The paper’s move is to do this at every node of the tree with the same W. Sharing W creates dependence, but disjointness along paths keeps it under control, and a potential function shows that the whole tree shrinks with probability at least 3/4. After about the log of h successful rounds, every leftover is empty. The random sets, failed rounds included, form one random graph, of density at most 2048 e⁵⁰, times p_E, times one plus the base-two log of h, and it contains a copy of H with probability at least 2/3.

4:57Where it stands

The preprint is not peer reviewed and has not been revised. OpenAI’s Lean files state the theorem with the same explicit constants, counting ordinary copies, and prove it in 37 files and about 6,800 lines, with no gaps we could find by search; we did not run the check. It is not among the papers OSVerify reviewed, and we have seen no expert review. If it holds, the second Kahn–Kalai conjecture is true: a graph appears in a random graph once every piece of it is expected, up to a fixed constant and the logarithm of its number of edges.

Spot a mistake?

This episode simplifies on purpose, but it shouldn’t be wrong. If something is, open an issue on GitHub or leave a comment on YouTube. Corrections are noted here with a date.