OctoInformBeta

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

Theorem 1.1: Two explicit bounds for graphs with an edge, using either the edge count or the ambient number of vertices

Critical thresholds obey logarithmic expectation bounds.

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

The comparison concerns the appearance of a fixed finite simple graph HH in a product random graph on nn vertices. Write v(H)=|V(H)|v(H)=|V(H)| for its number of vertices and h=e(H)h=e(H) for its number of unordered edges.

For a nonnegative integer nn, let [n]={1,…,n}[n]=\{1,\ldots,n\}. The edges of the complete graph on [n][n] form the set EnE_n in (1): En={{i,j}:i,j∈[n],i≠j}.E_n=\bigl\{\{i,j\}:i,j\in[n],\ i\ne j\bigr\}.(1)✦ For W⊆EnW\subseteq E_n, the graph G(W)G(W) is the simple graph on [n][n] with edge set WW.✦ 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 the vertex sets and any isolated vertices.

The product measure μp\mu_p on subsets of a finite ground set XX, for p∈[0,1]p\in[0,1], includes each coordinate independently with probability pp. For a real parameter pp and a subset WW of a finite ground set XX, the Bernoulli subset weight is the product with a factor pp for each coordinate in WW and a factor 1−p1-p for each coordinate outside WW.✦ For p∈[0,1]p\in[0,1], this is the mass μp({W})\mu_p(\{W\}) in (2): μp({W})=∏x∈Wp∏x∈X\W(1−p),W⊆X.\mu_p(\{W\})= \prod_{x\in W}p\prod_{x\in X\setminus W}(1-p), \qquad W\subseteq X.(2)✦ Let 𝒫(X)\mathcal P(X) denote the power set of XX. For a real parameter pp and a function f:𝒫(X)→ℝf:\mathcal P(X)\to\mathbb R, the Bernoulli expectation 𝔼μpf(W)\mathbb E_{\mu_p}f(W) is the sum of the Bernoulli subset weights multiplied by f(W)f(W) over all subsets WW of XX.✦ For p∈[0,1]p\in[0,1], this expectation and the probability μp(A)\mu_p(A) of an event A⊆𝒫(X)A\subseteq\mathcal P(X) are the sums in (3): 𝔼μpf(W)=∑W⊆Xμp({W})f(W),μp(A)=∑W∈Aμp({W}).\mathbb E_{\mu_p}f(W)= \sum_{W\subseteq X}\mu_p(\{W\})f(W), \qquad \mu_p(A)=\sum_{W\in A}\mu_p(\{W\}).(3) The random graph G(n,p)G(n,p) is G(W)G(W) for W⊆EnW\subseteq E_n sampled from μp\mu_p.

For a nonnegative integer nn, a real parameter pp and a finite simple graph FF, the expected copy count M(n,p,F)M(n,p,F) is the Bernoulli expectation at pp of N(G(W),F)N(G(W),F) over subsets WW of EnE_n.✦ For p∈[0,1]p\in[0,1], it is the expected number of ordinary unlabelled non-induced subgraphs of G(n,p)G(n,p) isomorphic to FF, including their vertex sets and any isolated vertices✦; the containment probability θ(n,p,H)\theta(n,p,H) is the probability that G(n,p)G(n,p) contains a subgraph isomorphic to a finite simple graph HH, as in (4): M(n,p,F)=𝔼μpN(G(W),F),θ(n,p,H)=μp({W⊆En:N(G(W),H)>0}).\begin{aligned} M(n,p,F)&=\mathbb E_{\mu_p}N(G(W),F),\\ \theta(n,p,H)&=\mu_p\bigl(\{W\subseteq E_n:N(G(W),H)>0\}\bigr). \end{aligned}(4) The critical threshold pc(n,H)p_c(n,H) is the infimum in (5) of the parameters whose containment probability is at least one-half: pc(n,H)=inf⁡{p∈[0,1]:θ(n,p,H)≥12}.p_c(n,H)=\inf\bigl\{p\in[0,1]:\theta(n,p,H)\ge\tfrac12\bigr\}.(5)✦ The expectation threshold pE(n,H)p_E(n,H) is the infimum in (6) of the parameters for which every actual subgraph FF of HH has expected copy count at least one-half: pE(n,H)=inf⁡{p∈[0,1]:M(n,p,F)≥12 for every subgraph F⊆H}.p_E(n,H)=\inf\bigl\{p\in[0,1]: M(n,p,F)\ge\tfrac12\text{ for every subgraph }F\subseteq H\bigr\}.(6)✦

The Bound Conditions

The base-two logarithm is denoted by log⁡2\log_2, as in (7), and exp⁡(50)=e50\exp(50)=e^{50}: log⁡2x=log⁡xlog⁡2.\log_2 x=\frac{\log x}{\log 2}.(7)✦ The threshold bound condition ℬ(n,H)\mathcal B(n,H) is the conjunction of the two inequalities in (8): ℬ(n,H):pc(n,H)≤min⁡{1,2048exp⁡(50)pE(n,H)(1+log⁡2h)},pc(n,H)≤6144exp⁡(50)pE(n,H)log⁡2n.\mathcal B(n,H):\qquad \begin{aligned} p_c(n,H)&\le \min\bigl\{1,\,2048\exp(50)\,p_E(n,H)(1+\log_2 h)\bigr\},\\ p_c(n,H)&\le6144\exp(50)\,p_E(n,H)\log_2 n. \end{aligned}(8)✦ The universal threshold statement 𝒮\mathcal S is the assertion in (9): 𝒮:for every integer n≥2 and finite simple graph Hwith v(H)≤n and e(H)≥1,ℬ(n,H) holds.\begin{gathered} \mathcal S:\quad \text{for every integer }n\ge2\text{ and finite simple graph }H\\ \text{with }v(H)\le n\text{ and }e(H)\ge1, \quad\mathcal B(n,H)\text{ holds}. \end{gathered}(9)✦

The Claim

Theorem 1. Let n≥2n\ge2 be an integer and let HH be a finite simple graph with at most nn vertices and at least one edge. The threshold bound condition is satisfied, as asserted in (10): ℬ(n,H).\mathcal B(n,H).(10)✦

The universal threshold statement asserts these bounds for every integer n≥2n\ge2 and every finite simple graph HH with v(H)≤nv(H)\le n and e(H)≥1e(H)\ge1: 𝒮.\mathcal S.(11)✦

What Is Checked

The statement ranges over finite simple graphs HH on at most nn vertices, with n≥2n\ge2 and e(H)≥1e(H)\ge1, and uses the product measure on the unordered pairs of distinct vertices of [n][n] and the ordinary subgraph counts N(G,F)N(G,F).