OpenAI preprint, September 2026 · §2. Conventions and preliminary results · §2
Cut expansion:Each
must send at least
edges to
,
with
all of
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 of vertices inside a graph, where each subset of is split off from the rest of .
Cuts
For a graph on a finite vertex set and a set , the cut of at is the set of edges of with one end in and the other in .
The cut edge count of two sets and of vertices of is the number of edges of with one end in and the other in .✦
The Definition
Definition 1. Let be a graph on a finite vertex set of order , and let be a real number. The graph has cut expansion at least if (1)✦ The graph has splitting cut expansion at least if (2)✦ The graph has sampling cut expansion at least if (3)✦For a set , the graph has sampling cut expansion at least on if (4)✦ The graph has scale cut expansion at least on if (5)✦ The graph has batch cut expansion at least on if (6)✦
In the paper, the result reads: a graph of order has cut expansion at least if for every .
What Is Checked
The six definitions are stated over a graph on a finite vertex set and a real number , the three on a set also over that set of vertices, with each cut inside measured by the cut edge count.