OctoInformBeta

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

Lemma 4.1: For large DD, graphs on D0.90≤r≤D1.02D^{0.90} \le r \le D^{1.02} vertices of cut expansion h≥cD0.90h \ge cD^{0.90} split into ll subgraphs of cut expansion at least h/(2l)h/(2l)

Splitting a strong expander into a fixed number of expanders.

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 PP be a graph on rr vertices with cut expansion at least hh, that is, every set UU of vertices sends at least hmin⁡{|U|,r−|U|}h \min\{|U|, r - |U|\} edges to the rest, and colour its edges with ll colours; the edges crossing any such cut are then shared among the ll sets of edges of one colour. The question is whether the colouring can be chosen so that every colour class still has cut expansion at least h/(2l)h/(2l), half of the h/lh/l that an even share of every cut would give it.

The question is posed at a large real scale DD, which bounds the order of PP and its expansion by powers of DD, with a constant c>0c > 0 and the number of colours ll fixed as DD grows.

Cut Expansion and Colour Classes

Graphs are simple, on a finite vertex set. For a graph HH on VV and a set U⊆VU \subseteq V, ∂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 vertex set VV of size rr has cut expansion at least a real number hh if every U⊆VU \subseteq V satisfies |∂HU|≥hmin⁡{|U|,r−|U|}.|\partial_H U| \ge h \min\{|U|,\, r - |U|\}.(1)✦

Let PP be a graph on VV, and let ω\omega assign to every pair of vertices of VV one of the colours 1,…,l1, \dots, l. The colour class PiP_i of colour ii is the spanning subgraph of PP on VV whose edges are the edges of PP of colour ii: E(Pi)={xy∈E(P):ω(xy)=i}.E(P_i) = \{\, xy \in E(P) : \omega(xy) = i \,\}.(2)✦

The Claim

Theorem 1. Let c>0c > 0 be a real number and ll a positive integer. For every sufficiently large real number DD the following holds. Let PP be a graph on a vertex set VV of size rr with D0.90≤r≤D1.02D^{0.90} \le r \le D^{1.02}, and let h≥cD0.90h \ge cD^{0.90} be a real number such that PP has cut expansion at least hh. Then there is a colouring ω\omega of the pairs of vertices of VV with the colours 1,…,l1, \dots, l whose colour classes P1,…,PlP_1, \dots, P_l satisfy E(P)=E(P1)∪…∪E(Pl),E(Pi)∩E(Pj)=∅(i≠j),|∂PiU|≥h2lmin⁡{|U|,r−|U|}for 1≤i≤l and every U⊆V.\begin{gathered} E(P) = E(P_1) \cup \dots \cup E(P_l), \qquad E(P_i) \cap E(P_j) = \emptyset \quad (i \ne j), \\ |\partial_{P_i} U| \ge \frac{h}{2l} \min\{|U|,\, r - |U|\} \quad \text{for } 1 \le i \le l \text{ and every } U \subseteq V. \end{gathered}(3)✦

In the paper, the result reads: for fixed c>0c > 0 and a positive integer ll and all sufficiently large DD, if an rr-vertex graph PP has cut expansion at least h≥cD0.90h \ge cD^{0.90} and D0.90≤r≤D1.02D^{0.90} \le r \le D^{1.02}, then its edge set can be partitioned into ll spanning subgraphs, each with cut expansion at least h/(2l)h/(2l).

What Is Checked

The claim (3) is stated over graphs on a finite vertex set, their cut expansion (1), and the colour classes (2) of a colouring of the pairs of vertices with ll colours, for real numbers c>0c > 0, DD and hh and a positive integer ll.