OctoInformBeta

OpenAI preprint, September 2026 · §6. Pair folding and resolving batches · §6

Lemma 6.2: Folding each active set XX cuts the order by ⌊|X|/2⌋\lfloor |X|/2\rfloor, and lifting quotient partitions costs at most 88 parts per active vertex

Folding paired vertices and resolving the 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

All graphs are simple graphs on finite vertex sets. The order |H||H| of a graph HH is the number of vertices of the vertex set that HH is on, isolated vertices included. A cycle-and-edge partition of a graph GG into kk parts is a partition of E(G)E(G) into kk sets, each the edge set of a cycle of GG or a single edge of GG.✦ The decomposition cost dc⁡(G)\operatorname{dc}(G) of GG is the least kk for which GG has a cycle-and-edge partition into kk parts.✦

The lemma is a step of an induction on the order that bounds the decomposition cost by a multiple of the order. The edges of a graph FF are shared among batches JbJ_b, each on a small vertex set WbW_b, and beside FF lie routers, graphs of large cut expansion on pairwise disjoint vertex sets. In each batch, sets of vertices of low degree, the active sets, each inside the vertex set of one router, are paired off and each pair is identified to one vertex; the batch folds to a quotient of smaller order, to which the induction applies. The question is how much order the folding saves, and how many extra parts it takes to turn cycle-and-edge partitions of the quotients into a partition of E(F)E(F), with some router edges, into cycles and single edges.

Pairings and Folded Quotients

A pairing of a set SS is a fixed-point-free involution pp of SS: p(p(x))=xp(p(x)) = x and p(x)≠xp(x) \ne x for every x∈Sx \in S.✦ The quotient S/pS/p of SS by a pairing pp is the set of classes of the equivalence relation u∼pv⇔u=vorp(u)=v,u \sim_p v \iff u = v \ \text{or}\ p(u) = v,(1)✦ and each of its classes is a pair {x,p(x)}\{x, p(x)\}. The projection of SS onto S/pS/p sends each element to its class.✦

For a finite set XX, let X+X^+ be XX itself when |X||X| is even and XX with one new point added when |X||X| is odd. A padded pairing of XX is a pairing of X+X^+.✦

Let (Xi)i∈I(X_i)_{i \in I} be pairwise disjoint subsets of a finite set VV, indexed by a finite set II, and let p=(pi)i∈Ip = (p_i)_{i \in I} be padded pairings of the XiX_i. The folded quotient V/pV/p is the disjoint union V/p=(V\⋃i∈IXi)⊔⨆i∈IXi+/piV/p = \Bigl(V \setminus \bigcup_{i \in I} X_i\Bigr) \sqcup \bigsqcup_{i \in I} X_i^+/p_i(2)✦ of the vertices outside all the XiX_i and the pairs of each Xi+X_i^+. The projection πp:V→V/p\pi_p \colon V \to V/p fixes each vertex outside all the XiX_i and sends a vertex of XiX_i to its class in Xi+/piX_i^+/p_i.✦ For an edge uvuv of a graph on VV, πp(uv)\pi_p(uv) is the pair {πp(u),πp(v)}\{\pi_p(u), \pi_p(v)\}.

Prepared Batches

Let GG be a graph on VV and (Xi)i∈I(X_i)_{i \in I} pairwise disjoint subsets of VV. A prepared batch for GG and (Xi)i∈I(X_i)_{i \in I} consists of padded pairings p=(pi)i∈Ip = (p_i)_{i \in I} of the XiX_i, a graph QQ on V/pV/p, the quotient of the batch, a set MM of retained edges and a set SS of set-aside edges of GG, and, for each ii, at most 2|Xi|2|X_i| paths of GG, each of length at least 22 with both ends in XiX_i, such that:✦

  1. the paths, over all ii, are pairwise edge-disjoint, and E(G)E(G) is the disjoint union of SS, MM and the edge sets of the paths;

  2. the edges of QQ are the pairs πp(e)\pi_p(e) with e∈Me \in M, and each edge of QQ is πp(e)\pi_p(e) for exactly one e∈Me \in M;

  3. the set SS and the order of QQ satisfy |S|≤6∑i∈I|Xi|,|S| \le 6 \sum_{i \in I} |X_i|,(3) |V/p|=|V|−∑i∈I⌊|Xi|2⌋.|V/p| = |V| - \sum_{i \in I} \Bigl\lfloor \frac{|X_i|}{2} \Bigr\rfloor.(4)

Cut Expansion on a Set

A graph HH on VV has cut expansion at least a real number hh on a set U⊆VU \subseteq V if eH(A,U\A)≥hmin⁡{|A|,|U\A|}for every A⊆U,e_H(A, U \setminus A) \ge h \min\{|A|, |U \setminus A|\} \quad \text{for every } A \subseteq U,(5)✦ where eH(A,B)e_H(A, B) is the number of edges of HH with one end in AA and the other in BB.

The Claim

Theorem 1.

  1. Let (Xi)i∈I(X_i)_{i \in I} be pairwise disjoint subsets of a finite set VV, each with at least two elements, and let pp be padded pairings of the XiX_i. Then |V/p|≤|V|−13∑i∈I|Xi|.|V/p| \le |V| - \frac{1}{3} \sum_{i \in I} |X_i|.(6)✦

  2. Let GG be a graph on a finite set VV, let (Xi)i∈I(X_i)_{i \in I} be pairwise disjoint subsets of VV, and let a≥1a \ge 1 be real. If for every i∈Ii \in I and every x∈Xix \in X_i |Xi|≥8,|Xi|≥a2,dG(x)≤a,|X_i| \ge 8, \qquad |X_i| \ge a^2, \qquad d_G(x) \le a,(7)✦ then GG and (Xi)i∈I(X_i)_{i \in I} have a prepared batch.

There is a real D0>1D_0 > 1 such that the following holds for every D≥D0D \ge D_0. Let FF be a subgraph of a graph GG on VV, and let (Ur)r∈ℛ(U_r)_{r \in \mathcal{R}} be pairwise disjoint subsets of VV, with ℛ\mathcal{R} finite and D0.90≤|Ur|≤D1.02D^{0.90} \le |U_r| \le D^{1.02}. Let (Jb)b∈B(J_b)_{b \in B}, with BB finite, be pairwise edge-disjoint subgraphs of FF whose edge sets cover E(F)E(F), and let Wb⊆VW_b \subseteq V be sets with |Wb|≤D0.30|W_b| \le D^{0.30} such that every edge of JbJ_b has both ends in WbW_b. For each bb, let (Xb,i)i∈Ib(X_{b,i})_{i \in I_b}, with IbI_b finite, be pairwise disjoint subsets of WbW_b, each contained in one of the sets UrU_r and such that dF(x)≤D0.01d_F(x) \le D^{0.01} for every x∈Xb,ix \in X_{b,i}.

  1. Let (Pr)r∈ℛ(P_r)_{r \in \mathcal{R}} be pairwise edge-disjoint subgraphs of GG, each edge-disjoint from FF and of cut expansion at least D0.90/4D^{0.90}/4 on UrU_r. For each bb, let a prepared batch for JbJ_b and (Xb,i)i∈Ib(X_{b,i})_{i \in I_b} be given whose quotient QbQ_b has a cycle-and-edge partition into kbk_b parts. Then there are a set E′E' of edges of the graphs PrP_r, disjoint from E(F)E(F), and a partition of E(F)∪E′E(F) \cup E' into mm parts, each the edge set of a cycle of GG or a single edge of GG, with m≤∑b∈Bkb+8∑b∈B∑i∈Ib|Xb,i|.m \le \sum_{b \in B} k_b + 8 \sum_{b \in B} \sum_{i \in I_b} |X_{b,i}|.(8)✦

  2. Let (Rr)r∈ℛ(R_r)_{r \in \mathcal{R}} be pairwise edge-disjoint subgraphs of GG, each edge-disjoint from FF, with all its edges inside UrU_r and of cut expansion at least D0.90D^{0.90} on UrU_r, such that E(G)=E(F)∪⋃rE(Rr)E(G) = E(F) \cup \bigcup_{r} E(R_r). Suppose that |Xb,i|≥8|X_{b,i}| \ge 8 and |Xb,i|≥D0.02|X_{b,i}| \ge D^{0.02} for all bb and ii, that nn is an integer with |Wb|<n|W_b| < n for every bb, and that t≥0t \ge 0 is a real number such that dc⁡(H)≤t|H|\operatorname{dc}(H) \le t|H| for every graph HH with |H|<n|H| < n and |H|≤D0.30|H| \le D^{0.30}. Then there are subgraphs Hr⊆RrH_r \subseteq R_r, each of cut expansion at least D0.90/4D^{0.90}/4 on UrU_r, such that dc⁡(G)≤t(∑b|Wb|−∑b∑i⌊|Xb,i|2⌋)+8∑b∑i|Xb,i|+∑rdc⁡(Hr).\operatorname{dc}(G) \le t \Bigl( \sum_{b} |W_b| - \sum_{b} \sum_{i} \Bigl\lfloor \frac{|X_{b,i}|}{2} \Bigr\rfloor \Bigr) + 8 \sum_{b} \sum_{i} |X_{b,i}| + \sum_{r} \operatorname{dc}(H_r).(9)✦

In the paper, the result reads: for every sufficiently large real DD, with a=D0.01a = D^{0.01}, L0=D0.03L_0 = D^{0.03}, B0=D0.30B_0 = D^{0.30} and σ=D0.90\sigma = D^{0.90}, let FF be the union of graphs JbJ_b with pairwise disjoint edge sets, each on a set WbW_b of at most B0B_0 vertices of a finite set VV, let RrR_r be graphs on pairwise disjoint subsets of VV, of orders between σ\sigma and D1.02D^{1.02} and edge-disjoint from FF, each with its edges split into two spanning graphs, the router PrP_r and TrT_r, both of cut expansion at least σ/4\sigma/4, and for some pairs (b,r)(b, r) let an active set Xb,r⊆Wb∩V(Rr)X_{b,r} \subseteq W_b \cap V(R_r) with |Xb,r|≥L0|X_{b,r}| \ge L_0 and dF(x)≤ad_F(x) \le a for x∈Xb,rx \in X_{b,r} be given, with ΣX=∑|Xb,r|\Sigma_X = \sum |X_{b,r}|; then there are quotient graphs QbQ_b of order qb=|Wb|−∑r⌊|Xb,r|/2⌋≤|Wb|−13∑r|Xb,r|≤B0q_b = |W_b| - \sum_r \lfloor |X_{b,r}|/2 \rfloor \le |W_b| - \frac{1}{3}\sum_r |X_{b,r}| \le B_0, so that ∑bqb≤∑b|Wb|−ΣX/3\sum_b q_b \le \sum_b |W_b| - \Sigma_X/3, such that for every choice of cycle-and-edge partitions of the QbQ_b into kbk_b parts there are sets Er′⊆E(Pr)E'_r \subseteq E(P_r) and a cycle-and-edge partition of E(F)∪⋃rEr′E(F) \cup \bigcup_r E'_r into at most ∑bkb+8ΣX\sum_b k_b + 8\Sigma_X parts, each Rr−Er′R_r - E'_r still contains TrT_r and so a spanning subgraph of cut expansion at least σ/4\sigma/4, and these parts together with the graphs Rr−Er′R_r - E'_r partition E(F)∪⋃rE(Rr)E(F) \cup \bigcup_r E(R_r). The library states the lemma in the four parts above, with the quotients QbQ_b taken from prepared batches.

What Is Checked

The claim is stated over graphs on finite vertex sets and their paths, padded pairings of pairwise disjoint vertex sets with the folded quotient V/pV/p and its projection πp\pi_p, prepared batches, cut expansion on a set, cycle-and-edge partitions into kk parts and the decomposition cost dc\operatorname{dc}. Beyond the claim, the library proves that, for pairwise disjoint XiX_i, VV is the disjoint union of the vertices outside all the XiX_i and the sets XiX_i.✦