OctoInformBeta

OpenAI preprint, September 2026 · Steps of the proof with no numbered result

Grouping graphs into batches: Pieces of order at most B/2B/2 and total order TT give at most 1+2T/B1+2T/B edge-disjoint batches of order at most BB

A graph split into small pieces splits into few batches.

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 the edges of a graph FF be split among edge-disjoint graphs HiH_i, the edges of HiH_i lying inside a vertex set UiU_i. When every UiU_i is small, there may be many such graphs. The question is how few graphs, each with its edges inside a set of at most BB vertices, for a positive real number BB, the edges of FF can be split among instead, if the sizes of these sets are to add up to no more than ∑i|Ui|\sum_i |U_i|. The library answers it when every UiU_i has at most B/2B/2 vertices.

Pieces and Batches

A piece (H,U)(H,U) on the vertex set of FF is a graph HH together with a set UU of vertices that contains both ends of every edge of HH; UU may hold vertices that meet no edge of HH. The order of the piece is |U||U|.

Let YY be a set of vertices of FF, and let BB and TT be real numbers. A batch family for FF, YY, BB and TT is a finite family of pieces (Fj,Wj)(F_j,W_j), j∈Jj\in J, the batches, in which the FjF_j are subgraphs of FF whose edge sets are pairwise disjoint with union E(F)E(F), the sets WjW_j lie in YY and cover it, and |Wj|≤B for every j∈J,∑j∈J|Wj|≤T,|J|≤1+2TB.|W_j|\le B \ \text{ for every } j\in J,\qquad \sum_{j\in J}|W_j|\le T,\qquad |J|\le 1+\frac{2T}{B}.(1)✦

The Claim

Theorem 1. Let FF be a graph, YY a set of its vertices and BB a positive real number. Let (Hi,Ui)(H_i,U_i), i∈Ii\in I, be a finite family of pieces such that the edge sets of the HiH_i are pairwise disjoint with union E(F)E(F), the sets UiU_i lie in YY and cover it, and every piece has order at most B/2B/2. Then there is a batch family for F, Y, B and T=∑i∈I|Ui|.\text{there is a batch family for $F$, $Y$, $B$ and } T=\sum_{i\in I}|U_i|.(2)✦

What Is Checked

The claim (2) is stated over a graph FF, a vertex set YY, a positive real number BB, a finite family of pieces (Hi,Ui)(H_i,U_i) whose graphs split the edges of FF edge-disjointly and whose sets lie in YY, cover it and have at most B/2B/2 elements each, and the batch families of (1).