OctoInformBeta

OpenAI preprint, September 2026 · §2. Conventions and preliminary results · §2

Cut expansion: Each U⊆WU \subseteq W must send at least hmin⁡{|U|,|W\U|}h\min\{|U|,|W\setminus U|\} edges to W\UW\setminus U, with WW all of VV or a part of it

Cut expansion of a graph and within a vertex set.

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

Split the vertices of a graph into two parts and count the edges that run between them. Cut expansion asks how small this count can be against the size of the smaller part, over all splits at once. Cut expansion is defined for a whole graph and for a set WW of vertices inside a graph, where each subset of WW is split off from the rest of WW.

Cuts

For a graph GG on a finite vertex set VV and a set U⊆VU \subseteq V, the cut ∂GU\partial_G U of GG at UU is the set of edges of GG with one end in UU and the other in V\UV \setminus U.

The cut edge count eG(X,Y)e_G(X, Y) of two sets XX and YY of vertices of GG is the number of edges of GG with one end in XX and the other in YY.✦

The Definition

Definition 1. Let HH be a graph on a finite vertex set VV of order rr, and let hh be a real number. The graph HH has cut expansion at least 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)✦ The graph HH has splitting cut expansion at least 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.(2)✦ The graph HH has sampling cut expansion at least 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.(3)✦ For a set W⊆VW \subseteq V, the graph HH has sampling cut expansion at least hh on WW 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.(4)✦ The graph HH has scale cut expansion at least hh on WW 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.(5)✦ The graph HH has batch cut expansion at least hh on WW 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.(6)✦

In the paper, the result reads: a graph HH of order rr has cut expansion at least hh if |∂HU|≥hmin⁡{|U|,r−|U|}|\partial_H U| \ge h \min\{|U|, r - |U|\} for every U⊆VU \subseteq V.

What Is Checked

The six definitions are stated over a graph on a finite vertex set and a real number hh, the three on a set WW also over that set of vertices, with each cut inside WW measured by the cut edge count eHe_H.