OctoInformBeta

OpenAI preprint, September 2026 · §4. Application to graph containment

§4 (setting): incident-vertex graphs and ordinary-copy ratios: Ordinary subgraph counts and expectation constraints for graph containment, including isolated vertices

Copy ratios and incident-vertex graph representations.

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

For a finite graph HH, consider the event that a random graph on nn vertices contains an ordinary, non-induced copy of HH. The question is how its containment and expectation constraints relate to the distinct edge sets obtained by permuting vertices.

Write [n]={0,…,n−1}[n]=\{0,\ldots,n-1\} and let KnK_n be the complete graph on [n][n]. An edge of KnK_n is an unordered pair of distinct vertices; write 𝒜n\mathcal A_n for the set of these edges.✦ For W⊆𝒜nW\subseteq\mathcal A_n, the graph GWG_W is the simple graph on all of [n][n] with edge set WW, including vertices incident to no edge.✦ The edge count e(H)e(H) is the number of unordered edges of HH.✦

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, including their vertex sets and any isolated vertices. An actual subgraph FF of HH is a graph specified by a vertex subset of V(H)V(H) and an edge subset of E(H)E(H) whose endpoints lie in that vertex subset.

For S⊆𝒜nS\subseteq\mathcal A_n, let V(S)V(S) be the set of endpoints of edges in SS. The incident-vertex subgraph LSL_S of KnK_n has vertex set V(S)V(S) and edge set SS.✦ The incident-vertex graph HSH_S is the simple graph on V(S)V(S) with the adjacency of LSL_S.✦

Copies and Their Laws

Let a finite group Γ\Gamma act on a finite set XX. The orbit of distinct copies of F⊆XF\subseteq X is the family 𝒞Γ(F)\mathcal C_\Gamma(F) in (1); an unlabelled copy of FF is a member of this family. The copy count cΓ(F)c_\Gamma(F) is the number of members of 𝒞Γ(F)\mathcal C_\Gamma(F), and the internal copy count cΓ(I,F)c_\Gamma(I,F) for I⊆XI\subseteq X is the number of members of 𝒞Γ(F)\mathcal C_\Gamma(F) contained in II: 𝒞Γ(F)={gF:g∈Γ},cΓ(F)=|𝒞Γ(F)|,cΓ(I,F)=|{J∈𝒞Γ(F):J⊆I}|.\mathcal C_\Gamma(F)=\{gF:g\in\Gamma\},\qquad c_\Gamma(F)=|\mathcal C_\Gamma(F)|,\qquad c_\Gamma(I,F)=|\{J\in\mathcal C_\Gamma(F):J\subseteq I\}|.(1) For the action of all permutations of [n][n] on 𝒜n\mathcal A_n, abbreviate these notations to 𝒞n\mathcal C_n, cnc_n and cn(I,F)c_n(I,F).

A finite probability law ww on a finite set Ω\Omega is a function assigning nonnegative weights w(ω)w(\omega) to outcomes ω∈Ω\omega\in\Omega, with ∑ω∈Ωw(ω)=1\sum_{\omega\in\Omega}w(\omega)=1.✦ The probability of an event A⊆ΩA\subseteq\Omega is ∑ω∈Aw(ω)\sum_{\omega\in A}w(\omega).✦ The uniform law on a nonempty finite set Ω\Omega is the probability law that assigns weight 1/|Ω|1/|\Omega| to every outcome.✦

The uniform copy law of I⊆XI\subseteq X is the uniform probability law on 𝒞Γ(I)\mathcal C_\Gamma(I).✦ The copy containment probability πΓ(I,U)\pi_\Gamma(I,U), for U⊆XU\subseteq X, is the probability under this law that a copy contains UU, as defined in (2): πΓ(I,U)=PrJ uniform in 𝒞Γ(I)(U⊆J).\pi_\Gamma(I,U)= \Pr_{J\text{ uniform in }\mathcal C_\Gamma(I)}(U\subseteq J).(2)✦

For a finite ground set XX and a real parameter ρ\rho, the Bernoulli subset weight bρ,X(W)b_{\rho,X}(W) of W⊆XW\subseteq X and the Bernoulli expectation Bρ,X(f)B_{\rho,X}(f) of a real-valued function ff on subsets of XX are defined by (3): bρ,X(W)=∏x∈X{ρ,x∈W,1−ρ,x∉W,Bρ,X(f)=∑W⊆Xbρ,X(W)f(W).b_{\rho,X}(W)=\prod_{x\in X} \begin{cases}\rho,&x\in W,\\1-\rho,&x\notin W,\end{cases} \qquad B_{\rho,X}(f)=\sum_{W\subseteq X}b_{\rho,X}(W)f(W).(3) For 0≤ρ≤10\le\rho\le1, the law μρ\mu_\rho includes each coordinate independently with probability ρ\rho; then bρ,X(W)=μρ(W)b_{\rho,X}(W)=\mu_\rho(W) and Bρ,X(f)=𝔼μρfB_{\rho,X}(f)=\mathbb E_{\mu_\rho}f.

For a finite simple graph FF, the expected unlabelled copy count ℰn(ρ,F)\mathcal E_n(\rho,F) is the Bernoulli expectation in (4): ℰn(ρ,F)=Bρ,𝒜n(W↦N(GW,F)).\mathcal E_n(\rho,F)= B_{\rho,\mathcal A_n}\bigl(W\mapsto N(G_W,F)\bigr).(4)✦ For 0≤ρ≤10\le\rho\le1, write G(n,ρ)=GWG(n,\rho)=G_W for WW drawn from μρ\mu_\rho on 𝒜n\mathcal A_n.

The Claim

Theorem 1. Let a finite group Γ\Gamma act on a finite set XX, let I,F⊆XI,F\subseteq X, and let F0∈𝒞Γ(F)F_0\in\mathcal C_\Gamma(F). Then πΓ(I,F0)=cΓ(I,F)cΓ(F).\pi_\Gamma(I,F_0)=\frac{c_\Gamma(I,F)}{c_\Gamma(F)}.(5)✦ For every nonnegative integer nn and every S⊆𝒜nS\subseteq\mathcal A_n, cn(S)=N(Kn,HS).c_n(S)=N(K_n,H_S).(6)✦ For every real ρ\rho and every S⊆𝒜nS\subseteq\mathcal A_n, ℰn(ρ,HS)=cn(S)ρ|S|.\mathcal E_n(\rho,H_S)=c_n(S)\rho^{|S|}.(7)✦ Let HH be a finite simple graph with |V(H)|≤n|V(H)|\le n, and let q∈ℝq\in\mathbb R. Suppose that ℰn(q,F)≥12\mathcal E_n(q,F)\ge\tfrac12 for every actual subgraph FF of HH. There is an edge set E⊆𝒜nE\subseteq\mathcal A_n satisfying |E|=e(H),for every W⊆𝒜n,N(GW,H)>0⇔there is T∈𝒞n(E) with T⊆W,for every S⊆E,cn(S)q|S|≥12.\begin{gathered} |E|=e(H),\\ \text{for every }W\subseteq\mathcal A_n,\qquad N(G_W,H)>0\ \Longleftrightarrow\ \text{there is }T\in\mathcal C_n(E)\text{ with }T\subseteq W,\\ \text{for every }S\subseteq E,\qquad c_n(S)q^{|S|}\ge\tfrac12. \end{gathered}(8)✦

What Is Checked

The ratio (5) is stated for finite group actions, the identities (6) and (7) for edge sets under vertex permutations of KnK_n, and the transfer (8) for finite graphs on at most nn vertices with expectation constraints on every actual subgraph.