OctoInformBeta

OpenAI preprint, September 2026 · §5. Splitting at a scale · §5

Lemma 5.1: For large DD and average degree at most DD: few long cycles, boxes of expanding pieces and residuals of average degree at most D0.95D^{0.95}

Splitting a graph into long cycles, expanders and sparser residuals.

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 GG be a graph on NN vertices with average degree at most DD, where DD is a large real number. Lemma 5.1 cuts E(G)E(G) at the scale DD. A few edge-disjoint cycles, each of length at least D1.01D^{1.01}, are taken out first.

The library states the lemma in two forms: for each graph and each large scale, a decomposition into long cycles, boxes with their pieces, and residual graphs, and a single choice of such a decomposition for all graphs on a given vertex set at all scales at once.

Pieces, Cuts and Edge Partitions

Throughout, VV is a finite set and a graph on VV is a simple graph with vertex set VV; e(H)e(H) denotes the number of edges of a graph HH. A graph HH on VV is supported on a set A⊆VA\subseteq V when every edge of HH has both ends in AA.✦

A piece on VV is a pair (A,H)(A,H) of a set A⊆VA\subseteq V and a graph HH on VV supported on AA.✦ The set AA may contain vertices that lie on no edge of HH; its size |A||A| is the order of the piece, and 2e(H)/|A|2e(H)/|A| is the average degree of the piece.

Let hh be a real number. A graph HH on VV has cut expansion at least hh on a set A⊆VA\subseteq V when every set U⊆AU\subseteq A satisfies |∂HU|≥hmin⁡{|U|,|A\U|},|\partial_H U| \ge h\min\{|U|,\,|A\setminus U|\},(1)✦ where |∂HU||\partial_H U| is the number of edges of HH with one end in UU and the other in A\UA\setminus U. A piece (A,H)(A,H) has cut expansion at least hh when HH has cut expansion at least hh on AA.

A finite family H1,…,HkH_1,\dots,H_k of graphs on VV, in which a graph may occur more than once, is an edge partition of a graph GG on VV when every pair of vertices xx, yy satisfies |{i≤k:xy∈E(Hi)}|={1if xy∈E(G),0otherwise.\bigl|\{\,i\le k : xy\in E(H_i)\,\}\bigr| = \begin{cases} 1 & \text{if } xy\in E(G),\\ 0 & \text{otherwise.}\end{cases}(2)✦ We then write E(G)=E(H1)⊔…⊔E(Hk)E(G)=E(H_1)\sqcup\dots\sqcup E(H_k).

Stage Splits

A cycle graph on VV is a graph KK on VV whose edges are exactly the edges of one cycle of KK.✦

A stage split of a piece (A,H)(A,H) on VV consists of a finite family 𝒞\mathcal C of cycle graphs on VV, a finite family 𝒴\mathcal Y of pieces (Y,GY)(Y,G_Y) on VV, called boxes, and, for each box, a finite family ℛY\mathcal R_Y of pieces (Q,R)(Q,R) on VV, called the pieces of the box, and a graph HYH_Y on VV, called its residual graph, such that E(H)=⨆K∈𝒞E(K)⊔⨆(Y,GY)∈𝒴E(GY),E(GY)=E(HY)⊔⨆(Q,R)∈ℛYE(R)for every box (Y,GY),E(H)=\bigsqcup_{K\in\mathcal C}E(K)\ \sqcup\bigsqcup_{(Y,G_Y)\in\mathcal Y}E(G_Y), \qquad E(G_Y)=E(H_Y)\ \sqcup\bigsqcup_{(Q,R)\in\mathcal R_Y}E(R) \quad\text{for every box } (Y,G_Y),(3)✦ and such that every YY is a subset of AA, nonempty when AA is, the sets YY cover AA, the sets QQ of the pieces of each box are pairwise disjoint subsets of YY, and each HYH_Y is supported on YY.

For a real number DD, with log\log the logarithm to base 22, a stage split of a piece (A,H)(A,H) is bounded at scale DD when |𝒞|≤|A|2D0.01and∑(Y,GY)∈𝒴|Y|≤(1+2log⁡D)|A|,|\mathcal C|\le\frac{|A|}{2D^{0.01}} \qquad\text{and}\qquad \sum_{(Y,G_Y)\in\mathcal Y}|Y|\le\Bigl(1+\frac{2}{\log D}\Bigr)|A|,(4)✦ and when every box has order at most D1.02D^{1.02}, every piece of a box has order between D0.90D^{0.90} and D1.02D^{1.02} and cut expansion at least D0.90D^{0.90}, and the residual graph of every box (Y,GY)(Y,G_Y) satisfies 2e(HY)/|Y|≤D0.952e(H_Y)/|Y|\le D^{0.95}.

The Claim

Theorem 1. There is a real number DspD_{\mathrm{sp}} with the following two properties.

(a) Let D≥DspD\ge D_{\mathrm{sp}} be a real number, and let (A,G)(A,G) be a piece on a finite set VV with AA nonempty and average degree at most DD. Then (A,G)(A,G) has a stage split that is bounded at scale DD and whose family 𝒞\mathcal C of cycle graphs satisfies e(K)≥D1.01for every K∈𝒞.e(K)\ge D^{1.01}\qquad\text{for every } K\in\mathcal C.(5)✦

(b) Let VV be a finite set. There is a choice, for every real number DD and every piece (A,H)(A,H) on VV, of a stage split sD(A,H)s_D(A,H) of (A,H)(A,H) such that sD(A,H)is bounded at scale DwheneverD≥Dsp,A≠∅,2e(H)|A|≤D.s_D(A,H)\ \text{is bounded at scale } D \quad\text{whenever}\quad D\ge D_{\mathrm{sp}},\ A\neq\emptyset,\ \frac{2e(H)}{|A|}\le D.(6)✦

In the paper, the result reads: there are absolute constants DspD_{\mathrm{sp}} and C0C_0, where one may take C0=2C_0=2, such that for every real D≥DspD\ge D_{\mathrm{sp}}, every graph GG on a nonempty vertex set of order NN with average degree at most DD admits a family 𝒞\mathcal C of edge-disjoint cycles of length at least D1.01D^{1.01} with |𝒞|≤N/(2D0.01)|\mathcal C|\le N/(2D^{0.01}) and a partition of the remaining edges into graphs GYG_Y on boxes YY covering V(G)V(G) with 1≤|Y|≤D1.021\le|Y|\le D^{1.02} and ∑|Y|≤(1+C0/log⁡D)N\sum|Y|\le(1+C_0/\log D)N, and, for each box YY, a partition of E(GY)E(G_Y) into graphs RR on pairwise disjoint sets Q⊆YQ\subseteq Y, each of cut expansion at least σ=D0.90\sigma=D^{0.90} and of order σ≤|Q|≤D1.02\sigma\le|Q|\le D^{1.02}, and a residual graph HYH_Y on all of YY with 2e(HY)/|Y|≤D0.952e(H_Y)/|Y|\le D^{0.95}, the cycles, pieces and residual graphs together partitioning E(G)E(G).

What Is Checked

The claims (5) and (6) are stated over pieces on a finite set and their cut expansion (1), edge partitions (2), cycle graphs, and stage splits (3) with their boundedness (4) at scale DD.