Graph containment and the second Kahn–Kalai conjecture

Source and verification

This article explains family 176 of the October 6, 2026 OpenAI collection. Research conclusions are attributed to its manuscripts. The review covers statements, introductions, and selected proof mechanisms; it is not an independent verification of the complete proofs.

🏷️ Containment and expected subgraph counts

Let $G(n,p)$ be the random graph on $n$ labeled vertices with independent edge probability $p$. For a fixed graph $F$, let $N(G,F)$ count ordinary subgraphs isomorphic to $F$; additional edges between their vertices are allowed.

For a target $H$ with $h=e(H)\ge 1$ and at most $n$ vertices, define $p_c(n,H)$ as the least $p$ for which $G(n,p)$ contains $H$ with probability at least $1/2$. Define $p_E(n,H)$ as the least $p$ for which

$$\begin{array}{c}\mathbb{E}N(G(n,p),F)\ge \frac{1}{2}\\ \text{for every }F\subseteq H.\end{array}$$

These are two distinct tests. Containment of $H$ implies containment of each $F$, and hence $p_E\le p_c$. Expected copies of $H$ alone do not suffice: a denser subgraph can be the stronger obstruction.

For a graph $F$ with $v$ vertices and $e$ edges, the exact normalization is

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

where $(n{)}_v=n(n-1)\cdots (n-v+1)$. Dividing by automorphisms counts each ordinary copy once.

🏷️ A uniform logarithmic comparison

Manuscript claim

For every such target and $n\ge 2$, put $L=1+{\log }_{2}h$. Then

$$\begin{array}{c}{p}_c(n,H)\\ \le \min \{1,KL{p}_E(n,H)\},\end{array}$$

with the explicit universal constant $K=2048e^{50}$. Consequently $p_c(n,H)\le 6144e^{50}{p}_E(n,H){\log }_{2}n$. (OpenAI, 2026)

The target may grow with $n$. The constant is independent of its degrees and structure. Changing the expected-count budget from $1/2$ to one changes $p_E$ by at most a factor two: a constraint with $e\ge 1$ edges changes its critical parameter by $2^{1/e}\le 2$.

A logarithmic gap is necessary in general. A perfect matching on an even number $n$ of vertices has expectation threshold of order $1/n$, whereas containment requires density of order $\log n/n$. Isolated vertices explain the larger scale. Indeed, the expected number of isolated vertices is

$$n(1-p{)}^{n-1}\approx n{e}^{-np},$$

which becomes small only near $np=\log n$. This calculation explains the obstruction; proving the full matching threshold requires more than the first moment of isolated vertices.

🏷️ Why the abstract threshold theorem is insufficient

For an increasing family, a containment cover consists of small witness sets with total cost at most $1/2$. Let $q$ and $q_f$ be its integral and fractional covering thresholds, as defined in Expectation-threshold covers. For graph containment,

$$p_E(n,H)\le q({\mathcal{F}}_H)\le q_f({\mathcal{F}}_H).$$

The direction matters. An upper bound in terms of $q$ does not immediately give an upper bound in terms of the smaller $p_E$.

The fractional graph threshold corresponds to requiring expected counts at least $N(H,F)/2$, not merely $1/2$. That extra multiplicity records all copies of $F$ supplied by one copy of $H$. The graph-specific problem is to avoid paying a second logarithm when passing from simple count constraints to a random host containing a complete target.

🏷️ Nested cores and an extension tree

Start with a nonempty edge subset $I$ of $H$. The proof selects a subgraph $S$ maximizing a suitably weighted conditional containment ratio. The first-moment constraints force $S$ to be smaller than $I$ by a fixed factor. Maximality also bounds the conditional probability that a prescribed set $J$ occurs among the added edges by

$$(C_0{p}_E(n,H){)}^{|J|}.$$

Such a bound is called a spread estimate: specifying many edges costs a probability exponentially small in their number. Repeating the core selection gives nested subgraphs. All possible copies and extension histories are retained in a tree whose arc labels are the newly added edges.

Along a single history, these labels are disjoint and their sizes grow geometrically. Keeping the full tree, rather than committing prematurely to one extension, gives flexibility when a random sample makes one branch inconvenient.

🏷️ Reusing a random set without losing dependence control

For one spread distribution of labels, plant a sampled source label into an independent random edge set $W$. Given their union, resample a target label from the posterior distribution. The portion of the target outside $W$ is contained in the source. The source proves that large remainders are exponentially unlikely and controls the change of probability law on coordinates outside the target.

The main construction performs this transition at every node using the same $W$. This reuse is what avoids paying a logarithmic sampling cost separately at each extension level. It also creates dependence that must be analyzed explicitly.

A recursive potential bounds the probability that too many descendant continuations fail. Below an arc, all later labels avoid that arc’s label, so the local change-of-measure bound applies to the entire descendant potential. Disjointness along histories is therefore a quantitative input, not just convenient notation.

One successful draw halves capacities throughout the tree. Only logarithmically many successful draws are needed before the retained target fits in the sampled union. The edge-count logarithm comes from this global reduction, while the spread constants remain universal.

🏷️ Key steps and proof outlines

A maximizing core is small and gives conditional spread

Put $q=p_E(n,H)$ and $\sigma =128q$. For a current nonempty edge set $I\subseteq H$, select $S\subseteq I$ maximizing

$$R_{\sigma }(I,S)={\sigma }^{-|S|}\mathbb{P}(S_0\subseteq \mathbf{I}),$$

where $\mathbf{I}$ is a uniformly sampled ordinary copy of $I$ and $S_0$ is a fixed copy of $S$. The empty set has value one. If $M(F)$ counts copies of $F$ in $K_n$ and $M(I,F)$ those in $I$, symmetry gives the exact probability $M(I,F)/M(F)$. (OpenAI, 2026)

For $r=|S|>0$ and $h_I=|I|$, the expected-count hypothesis gives $M(S)q^r\ge 1/2$, while $M(I,S)\le \left(\genfrac{}{}{0ex}{}{h_I}{r}\right)$. Hence

$$R_{\sigma }(I,S)\le 2\left(\genfrac{}{}{0ex}{}{h_I}{r}\right)128^{-r}.$$

If $r\ge h_I/17$, this is at most $2(17e/128{)}^r<1$. A maximizing core thus has $|S|<|I|/17$. Reversing the iterated core sequence produces extension sizes growing by a factor greater than sixteen.

For a uniform extension conditioned to contain $S_0$, specifying additional edges $J$ disjoint from $S_0$ costs

$$\frac{\mathbb{P}(S_0\cup J\subseteq \mathbf{I})}{\mathbb{P}(S_0\subseteq \mathbf{I})}\le {\sigma }^{|J|},$$

by the same maximality. This simultaneously establishes the small-core and spread properties. Every extension history is retained separately, even when two histories reach the same copy, giving a tree with disjoint arc labels along each path.

Posterior resampling shrinks labels while retaining recoverability

For an $a$-spread label law $\nu$ with labels $A_b$ of size at most $m$, independently draw a source label $A_c$ and a Bernoulli-$\rho$ set $W$. Plant the source by setting $Y=W\cup A_c$, then select a target with posterior weights

$$\mathbb{P}(b\mid Y)=\frac{{\nu }_b{\rho }^{-|A_b|}{1}_{A_b\subseteq Y}}{Z(Y)}.$$

The planted union has density $Z(Y)$ relative to the Bernoulli law, so $\mathbb{P}(Z(Y)<e^{-10m})\le e^{-10m}$. The retained remainder $T=A_b\setminus W$ satisfies two exact inclusions:

$$T\subseteq A_c\cap A_b,A_b\subseteq W\cup T.$$

The first preserves spread through the source; the second recovers the target after adding $W$. For fixed $b$, spread gives $\mathbb{P}(|A_c\cap A_b|=r)\le \left(\genfrac{}{}{0ex}{}{m}{r}\right)a^r$. If $a/\rho \le e^{-50}$, bounding the posterior denominator on its good event yields

$$\mathbb{P}(|T|>m/2,Z\ge e^{-10m})\le e^{10m}{2}^m{e}^{-25m}.$$

Together with the small-denominator event, local failure has probability at most $e^{-9m}$.

The outside-coordinate bound permits one sample for the whole tree

For every nonnegative function $f$ depending only on $W$ outside the target label $A_b$, the same calculation gives

$$\mathbb{E}[1_{\{\text{target}=b,Z\ge e^{-10m}\}}f(W)]\le e^{11m}{\nu }_b\mathbb{E}f(W).$$

The reason is exact independence: the required event $A_b\setminus A_c\subseteq W$ uses only coordinates inside $A_b$. This controls the bias in the target law; that law is not asserted to equal $\nu$ at a fixed $W$.

At a node with outgoing capacity $m_s$, let $d_v(W)$ be local failure mass and $t_{vb}(W)$ the successful target mass. Define backward from the leaves

$$D_v(W)=e^{m_s}\left(d_v(W)+\sum _b{t}_{vb}(W)D_b(W)\right).$$

A bad node has $D_v>1$. All descendant labels avoid the incoming target label, so $D_b$ depends only on its outside coordinates. The previous bound therefore gives

$$\mathbb{E}{D}_v\le e^{-8m_s}+e^{12m_s}\sum _b{\nu }_v(b)\mathbb{E}{D}_b.$$

Since capacities grow by sixteen, ${\sum }_{h<j}{m}_h\le m_j/15$. Expanding the recurrence bounds root failure by ${\sum }_j\exp (12{\sum }_{h<j}{m}_h-8m_j)<1/4$. Thus one shared sample halves every retained capacity with probability at least $3/4$.

Only one logarithmic number of successful draws is charged

Conditioning on retained children multiplies a level’s spread parameter by at most $(1-e^{-m}{)}^{-1}$. During repeated halvings, its positive capacities are distinct integers, so their product is bounded by ${\prod }_{m\ge 1}(1-e^{-m}{)}^{-1}<4$. Spread stays uniformly controlled.

After $s=\lfloor {\log }_{2}e(H)\rfloor +1$ successes, every remainder is empty. Each attempt succeeds conditionally with probability at least $3/4$, so expected waiting time is at most $4s/3$; Markov gives completion within $4s$ attempts with probability at least $2/3$. Their union has density at most $16e^{50}\sigma s$. Substituting $\sigma =128p_E$ yields the stated constant. Reusing each sample throughout the tree is what avoids charging another logarithm for its depth.

See Also

• Integral and fractional covers concerns rounding and decomposition, not the graph-specific expected-count comparison proved here.
• Threshold widths distinguishes the location of a containment threshold from the width of its probability transition.

🏷️ Manuscripts and verification scope

• The second Kahn–Kalai conjecture — pinned manuscript and companion source.

The family scope page describes selected formalization coverage. The page selects the actual containment and graph expectation thresholds, with the edge-count logarithm and its vertex-count consequence. No Lean build, axiom audit, or manuscript-to-formal-statement equivalence check was performed for these notes.

OpenAI collection provides prerequisites and the reading sequence; coverage register records completed and pending families.

🐻  OpenAI 2026. The second Kahn–Kalai conjecture.