Predicting graph appearance from the expected counts of all subgraphs

← All digests

Family 176 · Combinatorics
Importance 5/5 · Provisional editorial rating
Sources consulted 2026-10-11

1. The question

A random graph cannot usually contain a complicated target if even one of the target’s smaller subgraphs has almost no expected copies. This gives a basic necessary test: increase the edge density until every subgraph has a reasonable expected count.

How far above that elementary counting scale must one go before the entire target is likely to appear? The second Kahn–Kalai conjecture predicts that only a logarithmic factor is necessary, uniformly over all target graphs, including targets that grow with the host.

The manuscript claims this statement. Its bound uses the number of target edges inside the logarithm. The main challenge is coordinating many stages of an embedding without paying a separate logarithmic penalty at each stage. The paper organizes all possible extension histories in a tree and reuses the same random sample across its levels.

2. Background and essential definitions

The random graph $G(n,p)$ has vertices $1,\ldots,n$. Each possible edge is present independently with probability $p$. The target $H$ is a finite simple graph with at most $n$ vertices and at least one edge.

For graphs $G$ and $F$, let $N(G,F)$ count ordinary subgraphs of $G$ isomorphic to $F$. These copies are not required to be induced: additional host edges among the selected vertices are allowed.

The ordinary containment threshold is

$$p_c(n,H)=\inf\{p:\Pr(N(G(n,p),H)>0)\geq1/2\}.$$

The graph expectation threshold is

$$p_E(n,H)=\inf\{p:\mathbb E N(G(n,p),F)\geq1/2 \text{ for every }F\subseteq H\}.$$

The second definition tests every subgraph, not just $H$ itself. A dense small part of a target can be a stronger obstruction than the expected count of the whole target.

For a fixed graph $F$ with $v$ vertices and $a$ edges,

$$\mathbb E N(G(n,p),F) =\frac{(n)_v}{|\operatorname{Aut}(F)|}p^a.$$

Here $(n)_v=n(n-1)\cdots(n-v+1)$, and $\operatorname{Aut}(F)$ is the group of vertex permutations preserving adjacency. Dividing by its size prevents counting equivalent labelings as different copies.

If $H$ appears, then each $F\subseteq H$ appears. A nonnegative integer count has expectation at least its probability of being positive. Consequently,

$$p_E(n,H)\leq p_c(n,H).$$

The theorem asks how large the reverse comparison must be. The thresholds use probability and expected-count level one half; changing the expected-count level to one changes the relevant scale by at most a factor two.

3. Development history and previous partial results

Thresholds for fixed subgraphs are part of classical random-graph theory, beginning with Erdős and Rényi and developed systematically by Bollobás. The present problem is more uniform: the graph $H$ may change with $n$, and it may use every host vertex.

Spanning examples show why a logarithm is necessary. For a perfect matching on an even number $n$ of vertices, the graph expectation threshold has order $1/n$, while the actual containment threshold has order $\log n/n$. At the smaller scale, isolated host vertices obstruct a matching covering every vertex. Hamilton cycles exhibit the same kind of gap. The classical Erdős–Rényi matching paper is an early landmark.

Kahn and Kalai proposed both an abstract expectation-threshold conjecture and this graph-specific one. The abstract problem allows a cover by many possible containment patterns, rather than the copies of one chosen subgraph. Park and Pham resolved that abstract conjecture after the fractional theorem of Frankston, Kahn, Narayanan and Park.

The distinction is important. If $q(\mathcal F_H)$ denotes the integral cover threshold for containing $H$, then

$$p_E(n,H)\leq q(\mathcal F_H).$$

An upper bound in terms of the potentially larger quantity $q$ does not automatically give one in terms of $p_E$. Thus the first conjecture’s solution did not settle the second.

Mossel, Niles-Weed, Sun and Zadik obtained a logarithmic bound using a modified graph expectation parameter that also records how many copies of each test graph occur inside $H$. Dubroff, Kahn and Park obtained a three-logarithm general comparison and settled a low-density regime. Their later work treated additional test-graph classes.

Tran’s September 2026 manuscript reduced the general containment loss to two logarithms and settled several target classes. Its conditional extension distributions are a direct input to the strategy developed here. The present manuscript claims the single logarithm uniformly.

4. What the new manuscripts claim

Let $h=e(H)\geq1$ be the number of target edges. The manuscript states

$$p_c(n,H)\leq \min\left\{1, 2048e^{50}p_E(n,H)(1+\log_2 h) \right\}.$$

The symbol $e$ in the constant is the base of the natural logarithm, and $\log_2$ has base two. The constant is explicit and universal; it does not depend on $n$ or on the target.

Since a simple graph on at most $n$ vertices has at most $\binom n2$ edges, the result implies

$$p_c(n,H)\leq6144e^{50}p_E(n,H)\log_2 n.$$

The minimum with one in the first formula handles cases where the other expression exceeds the largest possible edge probability. The constants are deliberately very large; the significance is the uniform single-logarithm dependence.

The underlying containment argument actually reaches probability at least two thirds at the stated density. This is more than needed for the one-half definition of $p_c$, but the headline remains a threshold comparison, not a claim that the same fixed multiple gives probability tending to one in every asymptotic setting.

No bounded-degree, bounded-degeneracy or fixed-target hypothesis is imposed. Isolated vertices are permitted, subject to the total vertex bound. The target must have at least one edge so that the expectation parameter and logarithmic formulation are nontrivial.

5. Why the advance matters

Importance: 5/5. The claim resolves the graph-specific Kahn–Kalai conjecture at the correct general logarithmic scale. It says that elementary expected-copy obstructions almost determine when any graph can appear, despite the global compatibility needed to place all its edges together.

The perfect-matching example explains the strength and the limit of the statement. Counting can miss the last isolated vertices, creating a genuine logarithmic delay. The theorem claims there is no worse general obstruction, up to an absolute constant.

This is also a uniform result across targets that need very different embedding methods in individual cases. The same comparison applies to dense graphs, sparse graphs and spanning graphs. The proof’s reuse of randomness across a hierarchy is therefore valuable beyond improving a numerical exponent: it offers a way to coordinate many dependent extension choices without repeatedly paying for them.

6. The main idea

Find a core with controlled extensions

Begin with a nonempty edge subset of $H$. Select a smaller core by maximizing a suitably normalized probability that a fixed copy of that core lies inside a uniformly chosen copy of the larger graph.

The expected-count assumptions prevent the core from being almost as large as the original. Maximality also controls the distribution of the edges needed to extend it. Informally, no specified set $J$ of added edges is too likely:

$$\Pr(J\subseteq A)\leq a^{|J|}$$

for a parameter $a$ that is a universal multiple of $p_E(n,H)$. A distribution satisfying such inequalities is called spread. It behaves, for containment tests, as though its edges were dispersed rather than concentrated on a few compulsory choices.

Repeating the construction yields nested cores. All possible labeled copies and their possible extensions form a branching tree. Each branch describes a complete embedding history. The edge sets added along one branch are disjoint, and their sizes vary geometrically.

Replace a difficult set by a small remainder

The paper uses a Bayesian resampling idea. Take a source extension $A$, add an independent random edge set $W$, and then sample another compatible extension from the conditional distribution given the union.

The portion of the new extension outside $W$ is a remainder. It is also contained in the source extension. Spread estimates make large remainders unlikely, so one sample can reduce the unresolved part substantially while retaining control of its distribution.

For one extension this is a local step. For an entire embedding tree, conditioning can distort later choices. The manuscript therefore estimates the change in probability on coordinates outside the chosen extension. Along a branch, later added edges avoid earlier ones, making that estimate applicable to the remaining continuation.

Pay for the hierarchy once

A recursively defined potential measures the chance that too many continuations fail. The local resampling bounds are applied simultaneously at every node using the same $W$, rather than an independent new sample for each level.

The result is a reduction of every level’s unresolved capacity by about one half at a controlled cost. Repeating this only logarithmically many times in $h$ completes some branch, whose accumulated labels form a copy of $H$.

This is the source of the final logarithm. The graph hierarchy supplies many possible ways to extend, and the random samples reduce uncertainty across those ways together. A separate logarithmic payment at every nested scale would lose the claimed bound.

7. Scope, limitations, and open questions

The theorem concerns ordinary copies in independent-edge random graphs. Induced copies impose additional nonedge requirements and are not covered by this statement. Hypergraph analogues also require their own arguments.

The graph expectation threshold checks all subgraphs. Replacing it with the expected count of $H$ alone can miss a denser obstruction inside the target. The all-subgraph hypothesis is part of the theorem’s content.

The single logarithm is necessary for some targets, but often excessive for a particular graph class. Determining when it can be removed, and finding sharp constants or narrow transition windows, remain more detailed questions. The enormous universal constant here is not a practical estimate for a specific finite graph.

The proof does not depend on the companion integral–fractional equivalence in family 175; the manuscript cites that result as context. Its route instead builds the graph-specific extension hierarchy and proves the required simultaneous covering statement directly. This distinguishes the dependency structure from the nearby threshold results.

8. Sources and further reading

The manuscript states the graph expectation normalization explicitly and explains the distinction between the two Kahn–Kalai conjectures before introducing its extension tree.

Primary references include Kahn–Kalai’s original paper, Mossel–Niles-Weed–Sun–Zadik, Dubroff–Kahn–Park, and Tran’s conditional-extension approach. The related abstract cover notions are explained separately in family 175, while the definitions needed for the present graph theorem are included above.

Source manuscripts

• M1. OpenAI, The second Kahn–Kalai conjecture (September 24, 2026).

Sources consulted on 11 October 2026 at repository revision fd4aeeb. Download the manuscript citations.