OctoInformBeta

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

Lemma 4.1: Disjoint path labels with capacities increasing by a factor of at least sixteen

A spread tree from orbit count 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

Let a finite group GG act on a ground set XX. For a finite subset F⊆XF\subseteq X, its copy orbit 𝒪G(F)\mathcal O_G(F) is the set of distinct images under this action✦, and its orbit count oG(F)o_G(F) is the number of these images, as in (1): 𝒪G(F)={g⋅F:g∈G},oG(F)=|𝒪G(F)|.\mathcal O_G(F)=\{g\cdot F:g\in G\}, \qquad o_G(F)=|\mathcal O_G(F)|.(1) An unlabelled copy of FF is a member of 𝒪G(F)\mathcal O_G(F).✦

A finite probability law μ\mu on a finite set Ω\Omega is a real weight function wμw_\mu with nonnegative values summing to one.✦ For a finite probability law μ\mu on a finite set Ω\Omega, the probability of an event E⊆ΩE\subseteq\Omega is μ(E)=∑ω∈Ewμ(ω)\mu(E)=\sum_{\omega\in E}w_\mu(\omega).✦ A finite probability law μ\mu on a finite set Ω\Omega has full support if every weight is positive.✦ On a nonempty Ω\Omega, the uniform law assigns weight 1/|Ω|1/|\Omega| to each outcome.✦

The uniform copy law μI\mu_I of a finite subset I⊆XI\subseteq X is the uniform law on 𝒪G(I)\mathcal O_G(I).✦ The copy containment probability πI(S)\pi_I(S) of the uniform copy law μI\mu_I of a finite subset I⊆XI\subseteq X, for a finite S⊆XS\subseteq X, is the event probability in (2): πI(S)=μI({J∈𝒪G(I):S⊆J}).\pi_I(S)=\mu_I\bigl(\{J\in\mathcal O_G(I):S\subseteq J\}\bigr).(2)✦

Probability Trees

A probability tree TT on XX of depth kk is a finite rooted tree whose leaves all have depth kk, with a full-support probability law on the outgoing branches at each node and a finite subset of XX labelling each arc.✦ A tree of depth zero is a leaf. A full path PP of a probability tree TT is a complete history of branch choices from the root to a leaf; the leaf has one empty history.✦ The path union U(P)U(P) of a full path PP in a probability tree TT is the union of the arc labels LaL_a along PP, as in (3): U(P)=⋃a∈PLa.U(P)=\bigcup_{a\in P}L_a.(3)✦ A probability tree TT on XX is disjoint if the labels on each full path are pairwise disjoint.✦

Level capacities m1,…,mkm_1,\ldots,m_k of a probability tree TT on XX of depth kk are natural numbers bounding the cardinality of every arc label at the corresponding level.✦ Levels are numbered from one; the declarations index these levels from zero. For a real parameter σ\sigma, at a node with branch set BB, branch weights νb\nu_b and labels LbL_b, the label distribution is σ\sigma-spread if (4) holds for every finite J⊆XJ\subseteq X: ∑b∈BJ⊆Lbνb≤σ|J|.\sum_{\substack{b\in B\\J\subseteq L_b}}\nu_b\le\sigma^{|J|}.(4) A probability tree TT on XX of depth kk has level spread parameters a1,…,aka_1,\ldots,a_k if every outgoing label distribution at level ii is aia_i-spread.✦

Predecessors and Extensions

A real score ff on subsets of a finite set I⊆XI\subseteq X has a maximizing subset✦; write Mf(I)M_f(I) for a chosen subset attaining its maximum over all subsets of II.✦ For a finite subset I⊆XI\subseteq X and a real parameter σ\sigma, the predecessor score sI,σs_{I,\sigma} is the real function on finite subsets of XX given in (5), and the maximizing predecessor Mσ(I)M_\sigma(I) is a chosen subset of II maximizing this score over all subsets of II.✦ sI,σ(S)=πI(S)σ|S|,Mσ(I)=MsI,σ(I).s_{I,\sigma}(S)=\frac{\pi_I(S)}{\sigma^{|S|}}, \qquad M_\sigma(I)=M_{s_{I,\sigma}}(I).(5)

For nested finite sets A0⊆⋯⊆AdA_0\subseteq\cdots\subseteq A_d and an initial copy S0∈𝒪G(A0)S_0\in\mathcal O_G(A_0), the copy extension tree is the probability tree of depth dd that at level ii chooses a copy Si∈𝒪G(Ai)S_i\in\mathcal O_G(A_i) under the uniform copy law conditioned on containing Si−1S_{i-1}, labels the arc by Si\Si−1S_i\setminus S_{i-1}, and continues from SiS_i.✦

The Claim

Theorem 1. Let H⊆XH\subseteq X be finite and nonempty, and let q>0q>0. Suppose oG(F)q|F|≥12o_G(F)q^{|F|}\ge\tfrac12 for every nonempty F⊆HF\subseteq H. There exist an integer k≥1k\ge1, a probability tree TT on XX of depth kk and capacities m1,…,mkm_1,\ldots,m_k satisfying (6): T is disjoint and has capacities m1,…,mk,T has spread 128q at every level,1≤mi(1≤i≤k),16mi≤mi+1(1≤i<k),mk≤|H|,U(P)∈𝒪G(H)for every full path P of T.\begin{gathered} T\text{ is disjoint and has capacities }m_1,\ldots,m_k,\\ T\text{ has spread }128q\text{ at every level},\\ 1\le m_i\quad(1\le i\le k),\qquad 16m_i\le m_{i+1}\quad(1\le i<k),\qquad m_k\le |H|,\\ U(P)\in\mathcal O_G(H)\quad\text{for every full path }P\text{ of }T. \end{gathered}(6)✦

In the paper, the result reads: for a graph HH with at least one edge and at most nn vertices, with expectation threshold q=pE(n,H)∈[0,1]q=p_E(n,H)\in[0,1] at budget one-half and σ=128q\sigma=128q, there is a disjoint probability tree on X=([n]2)X=\binom{[n]}2 whose path unions are copies of HH with its isolated vertices removed, every level is σ\sigma-spread, and its label sizes ℓ1,…,ℓk\ell_1,\ldots,\ell_k satisfy 1≤ℓ11\le\ell_1, ℓi+1≥16ℓi\ell_{i+1}\ge16\ell_i for 1≤i<k1\le i<k, and ℓk≤h=e(H)\ell_k\le h=e(H).

What Is Checked

The tree assertion is stated over a finite group action, a finite nonempty subset H⊆XH\subseteq X and a positive qq satisfying the orbit count hypothesis.

For a nonempty finite I⊆XI\subseteq X and q>0q>0 satisfying oG(S)q|S|≥12o_G(S)q^{|S|}\ge\tfrac12 for every nonempty S⊆IS\subseteq I, the maximizing predecessor satisfies (7): 17|M128q(I)|<|I|.17\,|M_{128q}(I)|<|I|.(7)✦

Let I⊆XI\subseteq X be finite and σ>0\sigma>0. For a copy S0∈𝒪G(Mσ(I))S_0\in\mathcal O_G(M_\sigma(I)) and a finite J⊆XJ\subseteq X disjoint from S0S_0, the conditional containment bound is (8): πI(S0∪J)πI(S0)≤σ|J|.\frac{\pi_I(S_0\cup J)}{\pi_I(S_0)}\le\sigma^{|J|}.(8)✦

Every full path PP of the copy extension tree for A0⊆⋯⊆AdA_0\subseteq\cdots\subseteq A_d and S0∈𝒪G(A0)S_0\in\mathcal O_G(A_0) satisfies (9): S0∪U(P)∈𝒪G(Ad).S_0\cup U(P)\in\mathcal O_G(A_d).(9)✦