OctoInformBeta

OpenAI preprint, September 2026 · §1. Graph thresholds and the main result

§1 (setting): ordinary copies, product random graphs, and the two thresholds: Attainment when the target has at most as many vertices as the host, and positive expectation thresholds when the target has an edge

Graph thresholds for ordinary copies.

Hover over a blue or green term in the text, or a node in the graph, to find it in the other. Select it to read its declaration both in Lean and in words.

The Setting

Let HH be a finite simple graph on a vertex set VV, and let nn be a nonnegative integer. Let KnK_n be the complete graph on nn vertices. The containment problem asks for the probability that the graph obtained by retaining each edge of KnK_n independently with probability p∈[0,1]p\in[0,1] contains an ordinary copy of HH.

For a finite ground set XX, a real parameter ρ\rho and a subset W⊆XW\subseteq X, the Bernoulli weight wρ(W)w_\rho(W) is the product wρ(W)=∏x∈X{ρ,x∈W,1−ρ,x∉W.w_\rho(W)=\prod_{x\in X} \begin{cases} \rho,&x\in W,\\ 1-\rho,&x\notin W. \end{cases}(1)✦ For a finite ground set XX, a real parameter ρ\rho and a function f:2X→ℝf:2^X\to\mathbb R, the Bernoulli expectation 𝔼ρ[f]\mathbb E_\rho[f] is the weighted sum of ff with the weights in (1): 𝔼ρ[f]=∑W⊆Xwρ(W)f(W).\mathbb E_\rho[f]=\sum_{W\subseteq X}w_\rho(W)f(W).(2)✦ The Bernoulli probability ℙρ(𝒜)\mathbb P_\rho(\mathcal A) of an event 𝒜⊆2X\mathcal A\subseteq2^X, for a finite ground set XX and a real parameter ρ\rho, is the sum of the Bernoulli weights of the subsets in 𝒜\mathcal A, where 𝟏𝒜(W)\mathbf1_{\mathcal A}(W) is 11 when W∈𝒜W\in\mathcal A and 00 otherwise: ℙρ(𝒜)=∑W⊆Xwρ(W)𝟏𝒜(W).\mathbb P_\rho(\mathcal A) =\sum_{W\subseteq X}w_\rho(W)\mathbf1_{\mathcal A}(W).(3)✦ For ρ∈[0,1]\rho\in[0,1], let μρ\mu_\rho be the distribution on subsets of XX obtained by including each element independently with probability ρ\rho; (2) and (3) are expectation and probability under μρ\mu_\rho.

Write [n]={1,…,n}[n]=\{1,\ldots,n\}. The edge set EnE_n of KnK_n consists of the unordered pairs of distinct vertices: En={{u,v}:u,v∈[n],u≠v}.E_n=\bigl\{\{u,v\}:u,v\in[n],\ u\ne v\bigr\}.(4)✦ For a subset WW of the edge set (4), the graph GWG_W is the simple graph with vertex set [n][n] and edge set WW: GW=([n],W).G_W=([n],W).(5)✦ The product random graph G(n,p)G(n,p) is the graph in (5) when WW has distribution μp\mu_p on subsets of EnE_n.

For finite simple graphs GG and FF, let N(G,F)N(G,F) be the number of ordinary unlabelled non-induced subgraphs of GG isomorphic to FF, counting their vertex sets and any isolated vertices. Write h=e(H)=|E(H)|h=e(H)=|E(H)| for the number of unordered edges of HH.✦

For a finite simple graph FF, the expected copy count ℰn,p(F)\mathcal E_{n,p}(F) in G(n,p)G(n,p) is the Bernoulli expectation (2) of N(GW,F)N(G_W,F): ℰn,p(F)=𝔼p[N(GW,F)],W⊆En.\mathcal E_{n,p}(F)=\mathbb E_p\bigl[N(G_W,F)\bigr], \qquad W\subseteq E_n.(6)✦ For a finite simple graph HH, the containment probability Cn,H(p)C_{n,H}(p) in G(n,p)G(n,p) is the Bernoulli probability (3) that GWG_W contains at least one ordinary copy of HH: Cn,H(p)=ℙp(N(GW,H)>0),W⊆En.C_{n,H}(p)=\mathbb P_p\bigl(N(G_W,H)>0\bigr), \qquad W\subseteq E_n.(7)✦

The Claim

Definition 1 (Graph thresholds). The critical threshold pc(n,H)p_c(n,H) is the infimum of the parameters in [0,1][0,1] at which the containment probability (7) reaches the budget one-half: pc(n,H)=inf⁡{p∈[0,1]:Cn,H(p)≥12}.p_c(n,H)=\inf\bigl\{p\in[0,1]:C_{n,H}(p)\ge\tfrac12\bigr\}.(8)✦ For a finite simple graph HH and a nonnegative integer nn, the expectation threshold pE(n,H)p_E(n,H) is the infimum of the parameters in [0,1][0,1] at which the expected copy count (6) reaches the budget one-half for every actual subgraph FF of HH, with its own vertex set: pE(n,H)=inf⁡{p∈[0,1]:ℰn,p(F)≥12 for every subgraph F⊆H}.p_E(n,H)=\inf\bigl\{p\in[0,1]: \mathcal E_{n,p}(F)\ge\tfrac12\text{ for every subgraph }F\subseteq H\bigr\}.(9)✦

Theorem 1 (Attainment and positivity). Let HH be a finite simple graph with |V(H)|≤n|V(H)|\le n, and take the thresholds in (8) and (9). Then pc(n,H)∈[0,1],Cn,H(pc(n,H))≥12.p_c(n,H)\in[0,1], \qquad C_{n,H}\bigl(p_c(n,H)\bigr)\ge\tfrac12.(10)✦ pE(n,H)∈[0,1],ℰn,pE(n,H)(F)≥12for every subgraph F⊆H.p_E(n,H)\in[0,1], \qquad \mathcal E_{n,p_E(n,H)}(F)\ge\tfrac12 \quad\text{for every subgraph }F\subseteq H.(11)✦ If h≥1h\ge1, then pE(n,H)>0.p_E(n,H)>0.(12)✦

What Is Checked

The statements (10) and (11) concern finite simple target graphs HH with |V(H)|≤n|V(H)|\le n and independent edge subsets of EnE_n, with the additional hypothesis h≥1h\ge1 in (12).