OctoInformBeta

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

Reservoir preparation and the reservoir remainder: The classes have cut expansion min⁡{c,1}D0.90/6\min\{c,1\}D^{0.90}/6, the reservoirs D0.74D^{0.74}; at most 3r3r completed parts and the unused spokes number at most 9r9r

Three expanding colour classes with reservoirs, and what remains.

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 a vertex set VV of order rr, and let PP be a spanning subgraph of GG in which every set of vertices sends many edges to its complement. The reservoir steps of the proof of Lemma 4.3 of the OpenAI preprint on a linear cycle-and-edge decomposition of every graph colour the edges of PP with three colours and give each colour class a reservoir: a small set of vertices, well connected inside the class, to which every vertex outside the set is joined by two edges of the class, its spokes.

The first step builds the colouring and the reservoirs from the expansion of PP, for a large parameter DD, so that the classes and the reservoirs inside them still expand. The second step starts from edge-disjoint sets of edges of GG, the completed parts, covering every edge of GG except the spokes and the edges of each class inside its reservoir; it bounds the number of parts and of unused spokes, the spokes lying in no completed part, and places the edges still uncovered inside the reservoirs.

Cut Expansion, Colour Classes and Spokes

A graph HH on a vertex set VV of order rr has cut expansion at least a real number hh if |∂HU|≥hmin⁡{|U|,r−|U|}for every U⊆V,|\partial_H U| \ge h \min\{|U|,\, r - |U|\} \quad \text{for every } U \subseteq V,(1)✦ where |∂HU||\partial_H U| is the number of edges of HH between UU and V\UV \setminus U. A graph HH on VV has cut expansion at least hh on a set W⊆VW \subseteq V if eH(U,W\U)≥hmin⁡{|U|,|W\U|}for every U⊆W,e_H(U, W \setminus U) \ge h \min\{|U|,\, |W \setminus U|\} \quad \text{for every } U \subseteq W,(2)✦ where eH(A,B)e_H(A, B) is the number of edges of HH with one end in AA and the other in BB.

A colouring ω\omega of the pairs of vertices with three colours gives each unordered pair of vertices one of the colours 1,2,31, 2, 3. The colour class PiP_i of a graph PP on VV under ω\omega is the spanning subgraph of PP whose edges are the edges of PP that ω\omega colours ii.✦

For constants c,η>0c, \eta > 0, the reservoir expansion coefficient c′c' and the reservoir sampling probability pp are c′=16min⁡{c,1},p=min⁡{η/12,1/12}.c' = \tfrac{1}{6}\min\{c, 1\}, \qquad p = \min\{\eta/12,\, 1/12\}.(3)

The spokes of a set WW of vertices under a map f:V×{1,2}→Vf \colon V \times \{1,2\} \to V are the pairs {v,f(v,t)}\{v, f(v,t)\} with v∈V\Wv \in V \setminus W and t∈{1,2}t \in \{1,2\}.✦ The set SS of all reservoir spokes of three sets W1,W2,W3W_1, W_2, W_3 under maps f1,f2,f3f_1, f_2, f_3 is S=⋃i=13{{v,fi(v,t)}:v∈V\Wi,t∈{1,2}}.S = \bigcup_{i=1}^{3} \bigl\{\{v, f_i(v,t)\} : v \in V \setminus W_i,\ t \in \{1,2\}\bigr\}.(4)✦

The edges of a graph PP inside a set WW of vertices are the edges of PP with both ends in WW, the edge set E(P[W])E(P[W]) of the subgraph of PP induced on WW.✦

For a family (Cj)j∈I(C_j)_{j \in I} of sets of edges, the completed parts, the set of completed edges is the union C=⋃j∈ICjC = \bigcup_{j \in I} C_j.✦ The unused spokes form the set S\CS \setminus C.✦

The restriction of GG to a set EE of pairs of vertices is the spanning subgraph of GG whose edges are the edges of GG in EE.✦ Given graphs P1,P2,P3P_1, P_2, P_3 on VV, sets W1,W2,W3W_1, W_2, W_3 of vertices and completed edges CC, the residual graph RiR_i is the restriction of GG to E(Pi[Wi])\CE(P_i[W_i]) \setminus C.

The Claim

Theorem 1 (Reservoir preparation). Let c,η>0c, \eta > 0, with c′c' and pp as in (3). There is a real number D0D_0 such that the following holds for every D≥D0D \ge D_0. Let GG be a graph on a vertex set VV of order rr with D0.90≤r≤D1.02D^{0.90} \le r \le D^{1.02}, and let PP be a spanning subgraph of GG of cut expansion at least cD0.90cD^{0.90}. Then there are a colouring of the pairs of vertices with three colours, whose colour classes P1,P2,P3P_1, P_2, P_3 of PP are edge-disjoint subgraphs of GG, pairwise disjoint sets W1,W2,W3W_1, W_2, W_3 of vertices with |W1|+|W2|+|W3|≤ηr|W_1| + |W_2| + |W_3| \le \eta r, and maps f1,f2,f3f_1, f_2, f_3 from V×{1,2}V \times \{1,2\} to VV, such that for each colour ii Pi has cut expansion at least c′D0.90, and at least D0.74 on Wi,2≤|Wi|≤2pr,|Wi|<r,fi(v,1)≠fi(v,2),fi(v,t)∈Wi,vfi(v,t)∈E(Pi)for v∈V\Wi,t∈{1,2},|{(v,t):v∈V\Wi,fi(v,t)=w}|≤⌈8rpc′D0.90⌉for w∈V.\begin{gathered} P_i \text{ has cut expansion at least } c'D^{0.90}, \text{ and at least } D^{0.74} \text{ on } W_i,\\ 2 \le |W_i| \le 2pr, \qquad |W_i| < r,\\ f_i(v,1) \ne f_i(v,2), \quad f_i(v,t) \in W_i, \quad v f_i(v,t) \in E(P_i) \quad \text{for } v \in V \setminus W_i,\ t \in \{1,2\},\\ \bigl|\{(v,t) : v \in V \setminus W_i,\ f_i(v,t) = w\}\bigr| \le \Bigl\lceil \frac{8r}{p\,c'D^{0.90}} \Bigr\rceil \quad \text{for } w \in V. \end{gathered}(5)✦

Theorem 2 (Reservoir remainder). Let GG be a graph on a vertex set VV of order rr, let P1,P2,P3P_1, P_2, P_3 be pairwise edge-disjoint subgraphs of GG, let W1,W2,W3W_1, W_2, W_3 be sets of vertices, the reservoirs, and let f1,f2,f3f_1, f_2, f_3 be maps from V×{1,2}V \times \{1,2\} to VV such that vfi(v,t)v f_i(v,t) is an edge of PiP_i for every v∈V\Wiv \in V \setminus W_i and t∈{1,2}t \in \{1,2\}, with SS the set of spokes (4). Let (Cj)j∈I(C_j)_{j \in I} be at most 3r3r pairwise disjoint sets of edges of GG whose union CC contains every edge of GG outside SS and outside E(P1[W1])∪E(P2[W2])∪E(P3[W3])E(P_1[W_1]) \cup E(P_2[W_2]) \cup E(P_3[W_3]). Then |I|+|S\C|≤9r,|I| + |S \setminus C| \le 9r,(6)✦ and the edges of GG outside C∪SC \cup S are the edges of the residual graphs R1,R2,R3R_1, R_2, R_3.

What Is Checked

The claims (5) and (6) are stated over graphs on a finite vertex set and their spanning subgraphs, cut expansion (1) and cut expansion on a set (2), the colour classes of a colouring of the pairs with three colours, the reservoir expansion coefficient and sampling probability (3), the spoke set (4) and the edges inside a reservoir, and the completed edges, unused spokes and residual graphs of a family of completed parts.