OctoInformBeta

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

Lemma 4.2: For large DD, order in [D0.90,D1.02][D^{0.90}, D^{1.02}] and cut expansion c′D0.90c'D^{0.90} give cut expansion D0.74D^{0.74} on pp-sampled vertex sets, except with probability ε\varepsilon

Random vertex samples of large expanders are likely 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 of order rr with D0.90≤r≤D1.02D^{0.90} \le r \le D^{1.02} and cut expansion at least h=c′D0.90h = c'D^{0.90}, where c′>0c' > 0 is a constant and DD is a large parameter. Keep each vertex of PP independently with probability pp, a constant in (0,1)(0,1), and let V′V' be the set of kept vertices. The question is how much of the expansion of PP survives in the induced subgraph P[V′]P[V'] once DD is large, with a bound on the failure probability that holds for all such PP at once.

Cut Expansion

A graph PP on a finite vertex set VV of order r=|V|r = |V| has cut expansion at least a real number hh when every set U⊆VU \subseteq V satisfies |∂PU|≥hmin⁡{|U|,r−|U|},|\partial_P U| \ge h \min\{|U|,\, r - |U|\},(1)✦ where |∂PU||\partial_P U| is the number of edges of PP with one end in UU and the other in V\UV \setminus U.

For a set W⊆VW \subseteq V, a graph PP on VV has cut expansion at least hh on WW when its induced subgraph P[W]P[W] has cut expansion at least hh: every U⊆WU \subseteq W satisfies eP(U,W\U)≥hmin⁡{|U|,|W\U|},e_P(U, W \setminus U) \ge h \min\{|U|,\, |W \setminus U|\},(2)✦ where eP(U,W\U)e_P(U, W \setminus U) is the number of edges of PP with one end in UU and the other in W\UW \setminus U.

Random Vertex Samples

Bernoulli vertex sampling with parameter p∈[0,1]p \in [0,1] on a finite set VV is the product probability measure on {0,1}V\{0,1\}^V under which the coordinates ω(v)\omega(v), v∈Vv \in V, are independent and each equals 11 with probability pp.✦ The sampled vertex set of a point ω∈{0,1}V\omega \in \{0,1\}^V is V′={v∈V:ω(v)=1}V' = \{v \in V : \omega(v) = 1\}.✦

For a graph PP on VV, the set of neighbours of a vertex vv in a set A⊆VA \subseteq V is the set NP(v)∩AN_P(v) \cap A of vertices of AA adjacent to vv.✦

Let PP be a graph on VV of order rr, and let pp, hh and τ\tau be real numbers. A point ω∈{0,1}V\omega \in \{0,1\}^V is a good vertex sample for PP with parameters pp, hh, τ\tau when its sampled vertex set V′V' satisfies |V′|≤2prand|NP(v)∩V′|≥ph2for every v∈V,|V'| \le 2pr \qquad\text{and}\qquad |N_P(v) \cap V'| \ge \frac{ph}{2} \quad \text{for every } v \in V,(3)✦ and PP has cut expansion at least τ\tau on V′V'.

The Claim

Theorem 1. Let c′>0c' > 0, 0<p<10 < p < 1 and ε>0\varepsilon > 0 be real numbers. There is a real number D0D_0, depending only on c′c', pp and ε\varepsilon, with the following property. Let D≥D0D \ge D_0, and let PP be a graph on a finite vertex set VV whose order rr satisfies D0.90≤r≤D1.02D^{0.90} \le r \le D^{1.02} and which has cut expansion at least h=c′D0.90h = c'D^{0.90}. Then, for ω\omega drawn from Bernoulli vertex sampling with parameter pp on VV, Pr⁡[ω is not a good vertex sample for P with parameters p,h,τ=D0.74]≤ε.\Pr\bigl[\omega \text{ is not a good vertex sample for } P \text{ with parameters } p,\ h,\ \tau = D^{0.74}\bigr] \le \varepsilon.(4)✦

In the paper, the result reads: fix c′>0c' > 0 and p∈(0,1)p \in (0,1), let PP have order D0.90≤r≤D1.02D^{0.90} \le r \le D^{1.02} and cut expansion at least h=c′D0.90h = c'D^{0.90}, and select each vertex independently with probability pp to form V′V'; then with probability 1−o(1)1 - o(1) as D→∞D \to \infty, |V′|≤2pr|V'| \le 2pr, |NP(v)∩V′|≥ph/2|N_P(v) \cap V'| \ge ph/2 for every vv, and P[V′]P[V'] has cut expansion at least τ=D0.74\tau = D^{0.74}, the error being uniform over the stated graphs and orders.

What Is Checked

The claim (4) is stated over graphs on a finite vertex set and their cut expansion (1), over Bernoulli vertex sampling and the sampled vertex set, and over good vertex samples (3), built from the neighbours of a vertex in a set and from cut expansion on a set of vertices (2).