OctoInformBeta

OpenAI preprint, September 2026 · §4. Expansion in small reservoirs · §4

Lemma 4.3: For large DD, an rr-vertex graph with D0.90≤r≤D1.02D^{0.90}\le r\le D^{1.02} and a cut-expanding spanning subgraph needs at most 9r9r of them

Cycles and single edges up to a small residue.

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. The decomposition cost of GG is the least number of parts in a partition of E(G)E(G) into edge sets of cycles of GG and single edges of GG.

Here GG is large and well connected on a scale set by a parameter DD: its order rr lies between two powers of DD, and GG contains a spanning subgraph whose cut expansion, the least ratio of the number of edges leaving a nonempty proper vertex set to the size of the smaller of its two sides, is at least a constant times a power of DD. The question is how few vertices can carry the edges of GG left over by at most 9r9r pairwise edge-disjoint cycles and single edges of GG.

Cycle-or-edge Sets and Cut Expansion

A cycle-or-edge set of a graph GG on a vertex set VV is a set SS of unordered pairs of vertices of VV that is either the edge set of a cycle of GG or the set {e}\{e\} of a single edge ee of GG.✦

For a graph HH on a finite vertex set VV and a set U⊆VU \subseteq V, the edge boundary ∂HU\partial_H U is the set of edges of HH with one end in UU and the other in V\UV \setminus U. A graph HH on a finite 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|\} \qquad \text{for every } U \subseteq V.(1)✦

The Claim

Theorem 1. Let cc and η\eta be positive reals. There is a real number D0>1D_0 > 1 with the following property. Let 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 suppose that GG contains a spanning subgraph of cut expansion at least cD0.90cD^{0.90}. Then there are an integer k≤9rk \le 9r, cycle-or-edge sets S1,…,SkS_1, \dots, S_k of GG, subgraphs H1,H2,H3H_1, H_2, H_3 of GG and sets W1,W2,W3⊆VW_1, W_2, W_3 \subseteq V, each WbW_b containing both ends of every edge of HbH_b, such that the sets S1,…,Sk,E(H1),E(H2),E(H3)S_1, \dots, S_k, E(H_1), E(H_2), E(H_3) are pairwise disjoint and E(G)=⋃i=1kSi∪⋃b=13E(Hb),|Wb|<r(b=1,2,3),∑b=13|Wb|≤ηr.E(G) = \bigcup_{i=1}^{k} S_i \cup \bigcup_{b=1}^{3} E(H_b), \qquad |W_b| < r \quad (b = 1, 2, 3), \qquad \sum_{b=1}^{3} |W_b| \le \eta r.(2)✦

In the paper, the result reads: for fixed η>0\eta > 0 and c>0c > 0 and all sufficiently large DD, if GG is an rr-vertex graph with D0.90≤r≤D1.02D^{0.90} \le r \le D^{1.02} containing a spanning subgraph of cut expansion at least cD0.90cD^{0.90}, then E(G)E(G) has a partition into at most 9r9r completed parts, each a simple cycle or a single edge, and the edge sets of at most three residual simple graphs on pairwise disjoint subsets of V(G)V(G), each of order less than rr, with total order at most ηr\eta r. The completed parts correspond to the cycle-or-edge sets S1,…,SkS_1, \dots, S_k of the theorem. The theorem has exactly three residual graphs H1H_1, H2H_2, H3H_3, any of which may have no edges, and allows the sets W1W_1, W2W_2, W3W_3 to overlap.

What Is Checked

The claim (2) is stated over graphs on a finite vertex set, the cycle-or-edge sets of such a graph, and cut expansion (1).