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

1 · The essentials

Imagine a collection of points, with connections added at random, and a particular pattern of connections you want to find. The question is how dense those random connections must be before that pattern appears. A natural benchmark asks when every smaller pattern contained in the target has an average number of appearances of at least one half. The result bounds the target’s appearance threshold using this benchmark and the number of connections in the target. Specifically, the threshold is at most the benchmark multiplied by a universal constant and by one plus the base-two logarithm of that number. It applies to every finite pattern with at least one connection, provided there are enough points to accommodate it. The main result has a Lean formalization.

A picture to help (an imperfect image, not to be taken literally)

As an imperfect image, think of looking for a complete arrangement of ingredients in a randomly stocked pantry: checking that each required smaller combination is available on average gives a benchmark, but does not itself guarantee the whole arrangement. The result limits how far beyond a corresponding benchmark one must go for a random connection pattern; the pantry image is not a mathematical model of the theorem.

Why it matters

The result connects an appearance threshold for a whole graph to expected copy counts for all its subgraphs. Its correction factor depends logarithmically on the number of edges, and the same constant works for all graphs satisfying the hypotheses. The manuscript identifies this statement as the second Kahn–Kalai conjecture.

2 · Going further

Let $H$ be a finite simple graph with $h \geq 1$ edges and at most $n$ vertices. In the random graph $G (n, p)$ , the problem is to bound the threshold for containing an ordinary copy of $H$ . The benchmark $p_{E} (n, H)$ is the least density at which every subgraph of $H$ has expected copy count at least $1/2$ .

The main result states that the appearance threshold is at most $C p_{E} (n, H) (1 + lo g_{2} h)$ , where $C$ is universal. Thus the comparison uses information about every subgraph, not just the expected number of copies of $H$ itself. The multiplicative correction is expressed through the edge count $h$ .

The supplied abstract identifies this as the second Kahn–Kalai conjecture but does not describe the argument or its main technical idea. The main result has a Lean formalization; no finer breakdown of its formalization scope is supplied. Only one manuscript is provided, so there are no supplied companion manuscripts to relate to it.

Useful notions

Graphs, vertices, and edges
Subgraphs and copies of a graph
Random graphs and edge probability
Expected counts
Base-two logarithms

What was known before / what is new

Before

The source presents the statement as the second Kahn–Kalai conjecture. It supplies no account of earlier bounds, partial results, or the history of the conjecture.

New

The main manuscript establishes the stated upper bound for every finite simple graph with at least one edge and at most $n$ vertices. The bound uses the expectation benchmark multiplied by $1 + lo g_{2} h$ and a universal constant. This main result has a Lean formalization.

Limits and assumptions

The hypotheses require a finite simple graph $H$ , at least one edge, and at most $n$ vertices. The conclusion concerns ordinary copies and is an upper bound, not an exact threshold formula. The source gives neither a numerical value for the universal constant nor a description of the argument. It reports a Lean formalization of the main result but provides no further scope details, and it identifies no remaining open questions.

Mini glossary

Finite simple graph: A finite collection of vertices connected by edges, with no loops or multiple edges between a pair of vertices.
Random graph $G (n, p)$: A graph on $n$ vertices in which each possible edge is included independently with probability $p$ .
Ordinary copy: An occurrence of the target graph that requires its edges to be present without requiring its missing edges to remain absent.
Expected copy count: The average number of occurrences of a specified graph in the random graph.
Expectation threshold: Here, $p_{E} (n, H)$ is the least density at which every subgraph of $H$ has expected copy count at least one half.
Universal constant: A constant that is the same for every graph and parameter choice covered by the result.

Keywords : Random graphs · Expectation threshold · Kahn–Kalai conjecture

AI-generated explanation based on the manuscript. Unofficial. Refer to the manuscript for the authoritative version.

3 · Technical details and sources

Claim made in the manuscript (source text)

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_{E} (n, H) (1 + lo g_{2} h)$ , with universal C. Here $p_{E}$ is the least density at which every subgraph of H has expected copy count at least 1/2.

Verified by Lean: the Lean software checked the part of the reasoning described below, sometimes only part of the manuscript. This does not mean independent mathematicians have validated the result.

Scope of the Lean formalization (source text)

…

lean/docs/176.md

Manuscripts in this family

★

The second Kahn–Kalai conjecture

24/09/2026

Verified by Lean

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_{E} (n, H) (1 + lo g_{2} h)$ , where C is universal. Here $p_{E} (n, H)$ is the least density at which every subgraph of H has expected copy count at least one half.

PDF GitHub folder Lean formalization