The second Kahn–Kalai conjecture with an edge-count bound
OpenAI research collection · 1 manuscript · Source checked 2026-10-19
OpenAI's result summary
Proves the second Kahn–Kalai conjecture: for every finite simple graph H with h ≥ 1 edges and at most n vertices, its appearance threshold in G(n,p) is at most C p_{\mathrm E}(n,H)(1+\log_2 h), with universal C. Here p_{\mathrm E} is the least density at which every subgraph of H has expected copy count at least 1/2.
Read the manuscripts
Short excerpts below come from OpenAI's abstracts. The full abstract and original PDF preserve the paper's precise scope.
MANUSCRIPT 01
The second Kahn–Kalai conjecture
We prove the second Kahn–Kalai conjecture. For every finite simple graph H with h ≥ 1 edges and at most n vertices, the threshold for G(n,p) to contain an ordinary copy of H is at most C p_{\mathrm E}(n,H)(1+\log_2 h), where C is universal. Here p_{\mathrm E}(n,H) is the least density at which every subgraph of H has expected…
Full source abstract
We prove the second Kahn–Kalai conjecture. For every finite simple graph H with h ≥ 1 edges and at most n vertices, the threshold for G(n,p) to contain an ordinary copy of H is at most C p_{\mathrm E}(n,H)(1+\log_2 h), where C is universal. Here p_{\mathrm E}(n,H) is the least density at which every subgraph of H has expected copy count at least one half.
This PDF is listed in OpenAI's formalization catalogue. See the scope and dependencies before interpreting coverage.
New mathematical reasoning could help AI tackle harder scientific and computational problems. How reliably these skills transfer beyond mathematics will determine how much they contribute to general intelligence.