OctoInformBeta

OpenAI preprint, September 2026 · Steps of the proof with no numbered result · §7

The layers of the induction and their costs: When a piece has layers above a large cutoff D*D^*, and how costs per vertex for smaller graphs bound its cost through them

Layers of a piece and bounds on its decomposition cost.

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

Graphs are simple graphs on a finite vertex set; V(G)V(G) is the vertex set of a graph GG, E(G)E(G) its edge set and e(G)e(G) its number of edges. A cycle-and-edge partition of GG into kk parts is a partition of E(G)E(G) into pairwise disjoint sets E1,…,EkE_1, \dots, E_k, each the edge set of a cycle of GG or a single edge of GG. The decomposition cost c(G)c(G) of GG is the least kk for which GG has a cycle-and-edge partition into kk parts.

Given a bound of CC parts per vertex for every graph of smaller order, the question is what the pieces defined below cost and what layers of a piece, at scales that fall from its order down to a cutoff D*D^*, give for its cost.

Pieces and Stage Splits

Fix a finite vertex set VV. A graph GG on VV is supported on a set AA of vertices when every edge of GG has both ends in AA.✦ A piece Q=(AQ,GQ)Q = (A_Q, G_Q) on VV is a set AQA_Q of vertices together with a graph GQG_Q on VV supported on AQA_Q.✦ The set AQA_Q may contain isolated vertices of GQG_Q, and the order of QQ is |Q|=|AQ||Q| = |A_Q|.

A cycle graph on VV is a graph KK on VV whose edges are exactly the edges of one cycle in KK.✦ A list LL of graphs on VV is an edge partition of a graph GG on VV when, for any two vertices xx and yy, the number of members of LL in which xx and yy are adjacent, a member listed twice counted twice, is 11 if xyxy is an edge of GG and 00 otherwise.✦

For a real number hh, a graph GG on VV has cut expansion at least hh on a set AA of vertices when |∂GU|≥hmin⁡{|U|,|A\U|}for every U⊆A,|\partial_G U| \ge h \min\{|U|, |A \setminus U|\} \quad \text{for every } U \subseteq A,(1)✦ where |∂GU||\partial_G U| is the number of edges of GG with one end in UU and the other in A\UA \setminus U.

A stage split of a piece PP on VV consists of cycle graphs K1,…,KqK_1, \dots, K_q on VV, its cycles, and a list of pieces, its boxes, whose vertex sets lie in APA_P, are nonempty when APA_P is, and cover APA_P.✦ With each box BB come a list of pieces, the pieces of BB, whose vertex sets lie in ABA_B and are pairwise disjoint, and a graph HBH_B on VV supported on ABA_B, the remainder of BB. The cycles and the graphs GBG_B of the boxes together form an edge partition of GPG_P, and for each box BB the remainder HBH_B and the graphs GRG_R of the pieces RR of BB together form an edge partition of GBG_B.

For a real number DD, a stage split of PP is bounded at scale DD when it has at most |P|/(2D0.01)|P|/(2D^{0.01}) cycles, every piece RR of every box has D0.90≤|R|≤D1.02D^{0.90} \le |R| \le D^{1.02} and a graph GRG_R of cut expansion at least D0.90D^{0.90} on ARA_R, and the boxes satisfy ∑B|B|≤(1+2log⁡D)|P|,|B|≤D1.02,2e(HB)|B|≤D0.95,\sum_B |B| \le \Bigl(1 + \frac{2}{\log D}\Bigr)|P|, \qquad |B| \le D^{1.02}, \qquad \frac{2e(H_B)}{|B|} \le D^{0.95},(2)✦ where log\log is the logarithm to base 22, the sum runs over all boxes, and the other two bounds hold for every box BB.

Layers

Let θ=0.95\theta = 0.95.✦ The scales at a real number nn are the numbers Dj=nθjD_j = n^{\theta^j} for j=0,1,2,…j = 0, 1, 2, \dots.✦

A split system ss on VV assigns to every stage j=0,1,2,…j = 0, 1, 2, \dots and every piece QQ on VV a stage split sj(Q)s_j(Q) of QQ.✦ Given ss and a piece PP, the frontier ℱj\mathcal F_j at layer jj is a list of pieces: ℱ0\mathcal F_0 consists of PP alone, and ℱj+1\mathcal F_{j+1} is the list of the boxes of the stage splits sj(Q)s_j(Q), Q∈ℱjQ \in \mathcal F_j, listed one after another.✦

The pieces of level jj of a list LL of pieces are the pieces of all the boxes of the stage splits sj(Q)s_j(Q), Q∈LQ \in L, listed one after another.✦ Write ℛj\mathcal R_j for the pieces of level jj of ℱj\mathcal F_j, and ℛ<k\mathcal R_{<k} for the pieces from the first kk layers, the lists ℛ0,…,ℛk−1\mathcal R_0, \dots, \mathcal R_{k-1} in turn. Write 𝒦<k\mathcal K_{<k} for the list of the cycles of the stage splits sj(Q)s_j(Q) with Q∈ℱjQ \in \mathcal F_j and j<kj < k, and |𝒦<k||\mathcal K_{<k}| for the number of its members.✦

The vertex mass of a list LL of pieces is μ(L)=∑Q∈L|Q|\mu(L) = \sum_{Q \in L} |Q|, a piece listed several times counted each time.✦ The frontier mass at layer jj is Mj=μ(ℱj)M_j = \mu(\mathcal F_j), the total order of the pieces of the frontier ℱj\mathcal F_j. The piece mass at layer jj is Sj=μ(ℛj)S_j = \mu(\mathcal R_j)✦, the total order of the pieces of level jj of the frontier ℱj\mathcal F_j.

Layered splitting data for a piece PP of order nn on VV at a cutoff D*D^*, a real number, consist of a split system ss on VV and an integer m≥1m \ge 1, the number of layers, such that, with DjD_j the scales at nn and ℱj\mathcal F_j the frontiers of ss and PP, Dj≥D* for every j<mandDm<D*,D_j \ge D^* \text{ for every } j < m \quad\text{and}\quad D_m < D^*,(3)✦ the stage split sj(Q)s_j(Q) is bounded at scale DjD_j for every j<mj < m and every Q∈ℱjQ \in \mathcal F_j, and 2e(GQ)/|Q|≤Dj2e(G_Q)/|Q| \le D_j for every j≤mj \le m and every Q∈ℱjQ \in \mathcal F_j.

For real numbers ww and DD, the scale DD is ww-ready when D>1D > 1, log⁡D≥w\log D \ge w and 1D0.01≤1log⁡D,2D−0.009≤1log⁡D,D−0.87+4D−0.15≤1log⁡D,D0.001≤D0.302,8≤D0.03.\begin{gathered} \frac{1}{D^{0.01}} \le \frac{1}{\log D}, \qquad 2D^{-0.009} \le \frac{1}{\log D}, \qquad D^{-0.87} + 4D^{-0.15} \le \frac{1}{\log D},\\ D^{0.001} \le \frac{D^{0.30}}{2}, \qquad 8 \le D^{0.03}. \end{gathered}(4)✦

The constant η\eta is 1/(100⋅804)1/(100 \cdot 804), with 804=4(200+1)804 = 4(200 + 1).✦

The Claim

Theorem 1. There is a real number Λ>1\Lambda > 1 such that (a), (b) and (c) hold for every piece PP on a finite vertex set and every real number D*≥ΛD^* \ge \Lambda, and (d) holds for every such PP and every real number D*D^*. In (b), (c) and (d), layered splitting data for PP at cutoff D*D^* are given, with mm layers; DjD_j are the scales at |P||P|, and ℛ<k\mathcal R_{<k}, 𝒦<k\mathcal K_{<k}, MjM_j and SjS_j are those of the data.

  1. If |P|≥D*and2e(GP)|P|≤|P|,|P| \ge D^* \quad\text{and}\quad \frac{2e(G_P)}{|P|} \le |P|,(5)✦ then PP has layered splitting data at cutoff D*D^*.

  2. Let C≥0C \ge 0 be such that c(G)≤C|V(G)|c(G) \le C|V(G)| for every graph GG with |V(G)|<|P||V(G)| < |P|. Then, for every k≤mk \le m, every piece RR in ℛ<k\mathcal R_{<k} satisfies c(GR)≤(9+Cη)|R|.c(G_R) \le (9 + C\eta)|R|.(6)✦

  3. Let |P|>1|P| > 1, let every scale DjD_j with j<mj < m be 8080-ready, and let ii be a natural number with i+200<mi + 200 < m. Let C,t≥0C, t \ge 0 be such that every graph GG with |V(G)|<|P||V(G)| < |P| has c(G)≤C|V(G)|c(G) \le C|V(G)|, and has c(G)≤t|V(G)|c(G) \le t|V(G)| if also |V(G)|≤Di0.30|V(G)| \le D_i^{0.30}. If every piece RR in ℛ<i+201\mathcal R_{<i+201} satisfies c(GR)≤(9+Cη)|R|c(G_R) \le (9 + C\eta)|R|, then c(GP)≤|𝒦<i+201|+(9+Cη)μ(ℛ<i+201)+(t+8)Mi+201+(8−t3)Si+(2t3log⁡Di−8)Mi+1.\begin{split} c(G_P) \le{}& |\mathcal K_{<i+201}| + (9 + C\eta)\,\mu(\mathcal R_{<i+201}) + (t + 8)M_{i+201}\\ &+ \Bigl(8 - \frac{t}{3}\Bigr)S_i + \Bigl(\frac{2t}{3\log D_i} - 8\Bigr)M_{i+1}. \end{split}(7)✦

  4. Let |P|>1|P| > 1 and let every scale DjD_j with j<mj < m be 8080-ready. If β\beta is a real number with c(GR)≤β|R|c(G_R) \le \beta|R| for every piece RR in ℛ<m\mathcal R_{<m}, then c(GP)≤(20+D*)|P|+βμ(ℛ<m).c(G_P) \le (20 + D^*)|P| + \beta\,\mu(\mathcal R_{<m}).(8)✦

What Is Checked

The claim is stated over the decomposition cost c(G)c(G), pieces and their stage splits bounded at a scale, and layered splitting data at a cutoff D*D^* with their frontiers ℱj\mathcal F_j, the lists ℛ<k\mathcal R_{<k} and 𝒦<k\mathcal K_{<k}, the vertex masses MjM_j and SjS_j, the 8080-ready scales and the constant η\eta.