OctoInformBeta

OpenAI preprint, September 2026 · §7. The induction · §7

The potential φ, the scales and the layers: The potential φ\varphi, the scales Dj=nθjD_j = n^{\theta^j} with θ=0.95\theta = 0.95, and the splits of Lemma 5.1 iterated down to a cutoff

The potential, the scales and the layers of the induction.

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

A cycle-and-edge partition of a graph GG is a partition of the edge set of GG into parts, each the edge set of a cycle of GG or a single edge of GG; Erdős and Gallai conjectured that every graph on nn vertices has one with O(n)O(n) parts. The induction toward such a partition cuts a graph in layers. At the first layer the graph, of size nn, is split as in Lemma 5.1 of the preprint “A linear cycle-and-edge decomposition of every graph” (the paper), taking out a few cycles and leaving smaller pieces of large cut expansion; each of these is split again at a smaller size scale, layer after layer, until the scale falls below a cutoff.

The library defines the scales, the layers of splits down to a cutoff, and a potential φ\varphi of one real variable used by the induction.

Pieces and Splits

Fix a finite set VV of vertices. A graph GG on VV is supported on a set A⊆VA \subseteq V 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 AQ⊆VA_Q \subseteq V together with a graph GQG_Q on VV supported on AQA_Q; the set AQA_Q may hold isolated vertices of GQG_Q, and the order of QQ is |Q|=|AQ||Q| = |A_Q|.✦

Write e(G)e(G) for the number of edges of a graph GG✦ and, for U⊆AU \subseteq A, |∂GU||\partial_G U| for the number of edges of GG between UU and A\UA \setminus U✦. The graph GG has cut expansion at least hh on AA when |∂GU|≥hmin⁡{|U|,|A\U|}|\partial_G U| \ge h \min\{|U|, |A \setminus U|\} for every U⊆AU \subseteq A.✦

Given a graph GG on VV, a sequence G1,…,GmG_1, \dots, G_m of graphs on VV is an edge partition of GG when every edge of GG lies in exactly one of G1,…,GmG_1, \dots, G_m and none of them has an edge outside GG.✦ A cycle graph on VV is a graph on VV whose edges are exactly those of one cycle, every other vertex being isolated.✦

A stage split of a piece PP consists of cycle graphs K1,…,KcK_1, \dots, K_c on VV, a sequence of pieces called boxes, and for each box BB a sequence of pieces, the pieces of BB, together with a graph HBH_B on VV supported on ABA_B, the remainder of BB.✦ The vertex sets of the boxes lie in APA_P, are nonempty when APA_P is, and cover APA_P; the pieces of each box BB have pairwise disjoint vertex sets inside ABA_B. The graphs K1,…,KcK_1, \dots, K_c and the graphs GBG_B of the boxes 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 form an edge partition of GBG_B.

Given a real number DD, a stage split of PP is bounded at scale DD when, with log\log the base 2 logarithm, c≤|P|2D0.01,∑B|B|≤(1+2log⁡D)|P|,|B|≤D1.02,D0.90≤|R|≤D1.02,2e(HB)|B|≤D0.95\begin{gathered} c \le \frac{|P|}{2D^{0.01}}, \qquad \sum_B |B| \le \Bigl(1 + \frac{2}{\log D}\Bigr)|P|, \qquad |B| \le D^{1.02},\\ D^{0.90} \le |R| \le D^{1.02}, \qquad \frac{2e(H_B)}{|B|} \le D^{0.95} \end{gathered}(1)✦ for every box BB and every piece RR of BB, and every such GRG_R has cut expansion at least D0.90D^{0.90} on ARA_R.

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.✦ A split system ss on VV generates from a piece PP on VV layers of pieces: the layer ℒ0(P)\mathcal{L}_0(P) is PP alone, and ℒj+1(P)\mathcal{L}_{j+1}(P) consists of the pieces of the boxes of the stage splits sj(Q)s_j(Q) for Q∈ℒj(P)Q \in \mathcal{L}_j(P).

The Definition

Definition 1. The potential is the function φ\varphi on the real numbers given by φ(x)={1/2if x=1,max⁡{1/2,1−1/log⁡x}otherwise.\varphi(x) = \begin{cases} 1/2 & \text{if } x = 1,\\ \max\{1/2,\ 1 - 1/\sqrt{\log x}\} & \text{otherwise.} \end{cases}(2)✦ The scale exponent is the real number θ=0.95,\theta = 0.95,(3)✦ and the scale at a real number nn and a layer j=0,1,2,…j = 0, 1, 2, \dots is Dj=nθj.D_j = n^{\theta^j}.(4)✦ Let PP be a piece on VV of order nn, let D*D^* be a real number, and let DjD_j be the scales at nn. Layered splitting data for PP at the cutoff D*D^* consist of a split system ss on VV and an integer t≥1t \ge 1 such that Dj≥D* for j<t,Dt<D*,sj(Q) is bounded at scale Dj for j<t and Q∈ℒj(P),2e(GQ)|Q|≤Dj for j≤t and Q∈ℒj(P).\begin{gathered} D_j \ge D^* \text{ for } j < t, \qquad D_t < D^*,\\ s_j(Q) \text{ is bounded at scale } D_j \text{ for } j < t \text{ and } Q \in \mathcal{L}_j(P),\\ \frac{2e(G_Q)}{|Q|} \le D_j \text{ for } j \le t \text{ and } Q \in \mathcal{L}_j(P). \end{gathered}(5)✦

In the paper, the result reads: φ(1)=1/2\varphi(1) = 1/2 and φ(x)=max⁡{1/2,1−1/log⁡x}\varphi(x) = \max\{1/2,\ 1 - 1/\sqrt{\log x}\} for x>1x > 1, and Dj=nθjD_j = n^{\theta^j} with θ=0.95\theta = 0.95.

What Is Checked

The definitions (2), (3) and (4) are stated over the real numbers, and (5) over a piece on a finite vertex set and a real cutoff, with split systems on that set whose stage splits are held to the bounds (1) along the layers.