OctoInformBeta

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

Lemma 6.1: Suitable pairings of disjoint sets XiX_i and at most 2∑i|Xi|2\sum_i |X_i| set-aside edges give a simple quotient, each edge from exactly one retained edge

Folding vertex pairs in low-degree sets costs few edges.

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

Take a graph JJ on a finite vertex set VV and pairwise disjoint sets X1,…,XtX_1, \dots, X_t of its vertices, t≥0t \ge 0, each large compared with the degrees of its vertices and with the number of neighbours any vertex has in it. Pair up the vertices inside each XiX_i and identify each pair to a single vertex. An edge inside a pair becomes a loop, and two edges whose ends land on the same two vertices become parallel. The question is how few edges of JJ must be set aside, for a good choice of the pairings, for the rest to fold onto a simple graph. This is Lemma 6.1 of the preprint, the pair folding lemma.

Pairings and the Fold Map

A pairing pp of a finite set SS is a fixed-point-free involution of SS, a map p:S→Sp \colon S \to S with p(p(x))=xp(p(x)) = x and p(x)≠xp(x) \ne x for every x∈Sx \in S.✦ The pairs of pp are the classes {x,p(x)}\{x, p(x)\} of the equivalence relation on SS given by u∼pv⇔u=vorv=p(u).u \sim_p v \iff u = v \ \text{or} \ v = p(u).(1)✦ The quotient S/pS/p of SS by pp is the set of pairs of pp✦, and the projection S→S/pS \to S/p sends each xx to its pair [x]p[x]_p✦.

For a finite set XX of mm vertices, the padded set X+X^+ is XX itself when mm is even and XX with one new element *\ast added when mm is odd. A pairing pp of X+X^+ pairs up the vertices of XX and leaves mmod⁡2m \bmod 2 of them unpaired, the vertex p(*)p(\ast) when mm is odd✦.

The outside set OO of pairwise disjoint vertex sets X1,…,XtX_1, \dots, X_t of JJ is the set of vertices of JJ lying in none of them.✦ For p=(p1,…,pt)p = (p_1, \dots, p_t) with pip_i a pairing of Xi+X_i^+, the folded vertex set of pp is Vp=O⊔X1+/p1⊔…⊔Xt+/pt,V_p = O \sqcup X_1^+/p_1 \sqcup \dots \sqcup X_t^+/p_t,(2)✦ and the fold map π:V→Vp\pi \colon V \to V_p is given by π(v)=v(v∈O),π(x)=[x]pi(x∈Xi).\pi(v) = v \quad (v \in O), \qquad \pi(x) = [x]_{p_i} \quad (x \in X_i).(3)✦

The Claim

Theorem 1. Let JJ be a graph on a finite vertex set VV, let X1,…,XtX_1, \dots, X_t be pairwise disjoint subsets of VV, t≥0t \ge 0, with mi=|Xi|m_i = |X_i|, and let a≥1a \ge 1 be a real number. Suppose that mi≥max⁡{8,a2}m_i \ge \max\{8, a^2\} for every ii, that every vertex xx of X1∪…∪XtX_1 \cup \dots \cup X_t has degree dJ(x)≤ad_J(x) \le a, and that every vertex vv of JJ has at most aa neighbours in each XiX_i, |NJ(v)∩Xi|≤a|N_J(v) \cap X_i| \le a. Then there are pairings pip_i of the padded sets Xi+X_i^+, a set R⊆E(J)R \subseteq E(J) of retained edges and a graph QQ on the folded vertex set VpV_p of (2) such that, with π\pi the fold map (3), |E(J)\R|≤2∑i=1tmi,E(Q)={π(u)π(v):uv∈R},|Vp|=|V|−∑i=1t⌊mi/2⌋,\begin{gathered} |E(J) \setminus R| \le 2 \sum_{i=1}^{t} m_i, \qquad E(Q) = \{\pi(u)\pi(v) : uv \in R\}, \\ |V_p| = |V| - \sum_{i=1}^{t} \lfloor m_i/2 \rfloor, \end{gathered}(4)✦ and every edge of QQ is π(u)π(v)\pi(u)\pi(v) for exactly one edge uvuv of RR.

In the paper, the result reads: if JJ is a finite simple graph, X1,…,XtX_1, \dots, X_t are pairwise disjoint subsets of VV, a≥1a \ge 1, mi=|Xi|≥max⁡{8,a2}m_i = |X_i| \ge \max\{8, a^2\}, dJ(x)≤ad_J(x) \le a for every xx in ⋃iXi\bigcup_i X_i and |NJ(v)∩Xi|≤a|N_J(v) \cap X_i| \le a for every vv and ii, then there are pairings within the XiX_i, each leaving exactly mimod⁡2m_i \bmod 2 vertices unpaired, and a set Eerr⊆E(J)E_{\mathrm{err}} \subseteq E(J) with |Eerr|≤2∑imi|E_{\mathrm{err}}| \le 2\sum_i m_i such that identifying each pair in J−EerrJ - E_{\mathrm{err}} gives a simple graph QQ in which every edge has exactly one retained original edge as representative and |V(Q)|=|V|−∑i⌊mi/2⌋|V(Q)| = |V| - \sum_i \lfloor m_i/2 \rfloor, and this holds also when the family is empty. The paper’s EerrE_{\mathrm{err}} is E(J)\RE(J) \setminus R, and its pairings within the XiX_i are the pairings pip_i of the padded sets Xi+X_i^+.

What Is Checked

The claim (4) is stated over a graph JJ on a finite vertex set with pairwise disjoint vertex sets X1,…,XtX_1, \dots, X_t, the numbers |NJ(v)∩Xi||N_J(v) \cap X_i| of neighbours in them, the pairings of the padded sets Xi+X_i^+ with their quotients by the pair relation (1), the outside set OO, the folded vertex set VpV_p and the fold map π\pi. The library also proves that, for pairwise disjoint X1,…,XtX_1, \dots, X_t, the map from the disjoint union of O,X1,…,XtO, X_1, \dots, X_t to VV that sends each element to itself is a bijection.✦