OctoInformBeta

OpenAI preprint, September 2026 · §3. Pruning two families of pairs

The augmented graph, the cover and the choice of matching: A maximum matching of Γ\Gamma with at most |H|+|Z||H| + |Z| edges yields a pruning, and some maximum matching is maximum on both blocks

Pruning two families of pairs through the augmented graph.

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 →\to be a relation on a finite set XX, and let ℛ\mathcal R and 𝒞\mathcal C be two families of pairs in X×XX \times X. A pair (p,j)(p, j) of ℛ\mathcal R and a pair (i,s)(i, s) of 𝒞\mathcal C conflict when p→iands→j.p \to i \quad\text{and}\quad s \to j.(1)✦ The aim is to delete pairs from both families until no conflict is left, and to delete few.

Conflicts and Prunings

A conflict between (p,j)(p, j) and (i,s)(i, s) has the two points (i,j)(i, j) and (p,s)(p, s). The sets ZZ and HH of ℛ\mathcal R and 𝒞\mathcal C are the set of the points (i,j)(i, j) and the set of the points (p,s)(p, s) of all conflicts between a pair of ℛ\mathcal R and a pair of 𝒞\mathcal C. Families ℛ′\mathcal R' and 𝒞′\mathcal C' of pairs are conflict-free when no pair of ℛ′\mathcal R' conflicts with a pair of 𝒞′\mathcal C'.✦

A pair (p,j)(p, j) covers a pair (i,j)(i, j) from the left when p→ip \to i✦, and a pair (i,s)(i, s) covers (i,j)(i, j) from the right when s→js \to j✦. For a family SS of pairs, the left image F1SF_1 S is the set of the pairs covered from the left by a pair of SS✦, and the right image F2SF_2 S is the set of the pairs covered from the right by a pair of SS✦. A pair is covered by families ℛ′\mathcal R' and 𝒞′\mathcal C' when it lies in F1ℛ′∪F2𝒞′F_1\mathcal R' \cup F_2\mathcal C'.✦ The uncovered part of ZZ for ℛ′\mathcal R' and 𝒞′\mathcal C' is the set of the points of ZZ not covered by them, U(ℛ′,𝒞′)=Z\(F1ℛ′∪F2𝒞′).U(\mathcal R', \mathcal C') = Z \setminus (F_1\mathcal R' \cup F_2\mathcal C').(2)✦

A pruning of ℛ\mathcal R and 𝒞\mathcal C is a pair of conflict-free families ℛ′⊆ℛ\mathcal R' \subseteq \mathcal R and 𝒞′⊆𝒞\mathcal C' \subseteq \mathcal C that keep every pair of ℛ\mathcal R and of 𝒞\mathcal C that is in no conflict between the two families, and that satisfy |ℛ\ℛ′|+|𝒞\𝒞′|≤|H|+|U(ℛ′,𝒞′)|.|\mathcal R \setminus \mathcal R'| + |\mathcal C \setminus \mathcal C'| \le |H| + |U(\mathcal R', \mathcal C')|.(3)✦

Matchings and Vertex Covers

Let GG be a finite bipartite graph with left side LL and right side RR, an edge being a pair (l,r)∈L×R(l, r) \in L \times R. A matching of GG is a set of edges of GG no two of which share an end.✦ The matching number ν(G)\nu(G) is the largest number of edges in a matching of GG, and a maximum matching of GG is a matching with ν(G)\nu(G) edges.✦ A vertex cover of GG is a pair (A,B)(A, B) of sets A⊆LA \subseteq L and B⊆RB \subseteq R such that every edge (l,r)(l, r) of GG has l∈Al \in A or r∈Br \in B; its size is |A|+|B||A| + |B|.✦

For P⊆LP \subseteq L and Q⊆RQ \subseteq R, write P‾=L\P\bar P = L \setminus P and Q‾=R\Q\bar Q = R \setminus Q. An edge (l,r)(l, r) of GG starts in ll and ends in rr. The block GQG_Q is the bipartite graph on LL and RR whose edges are the edges of GG that end in QQ, and the block GP‾G_{\bar P} is the bipartite graph on LL and RR whose edges are the edges of GG that start in P‾\bar P. For a matching MM of GG, MQM_Q is the set of its edges that end in QQ and MP‾M_{\bar P} the set of its edges that start in P‾\bar P.

The Augmented Graph

The augmented graph Γ\Gamma of ℛ\mathcal R and 𝒞\mathcal C is the bipartite graph with left side ℛ⊔Z\mathcal R \sqcup Z and right side 𝒞⊔Z\mathcal C \sqcup Z, each side with its own copy of ZZ, in which a left vertex xx and a right vertex yy are joined when {x and y conflict,x∈ℛ,y∈𝒞,x covers y from the left,x∈ℛ,y∈Z,y covers x from the right,x∈Z,y∈𝒞,\begin{cases} x \text{ and } y \text{ conflict}, & x \in \mathcal R,\ y \in \mathcal C,\\ x \text{ covers } y \text{ from the left}, & x \in \mathcal R,\ y \in Z,\\ y \text{ covers } x \text{ from the right}, & x \in Z,\ y \in \mathcal C, \end{cases}(4)✦ and two points of ZZ are never joined.

The blocks of Γ\Gamma are the bipartite graph Γα\Gamma_\alpha between ZZ and ℛ\mathcal R, in which a point zz and a pair aa are joined when aa covers zz from the left✦, and the bipartite graph Γβ\Gamma_\beta between ZZ and 𝒞\mathcal C, in which zz and a pair bb are joined when bb covers zz from the right✦. A matching MM of Γ\Gamma has two parts: α\alpha, its edges from ℛ\mathcal R to ZZ, taken as edges of Γα\Gamma_\alpha✦, and β\beta, its edges from ZZ to 𝒞\mathcal C, taken as edges of Γβ\Gamma_\beta✦.

The Claim

Theorem 1. Let →\to be a relation on a finite set XX, and let ℛ\mathcal R and 𝒞\mathcal C be families of pairs in X×XX \times X.

  1. If Γ\Gamma has a maximum matching MM with |M|≤|H|+|Z|,|M| \le |H| + |Z|,(5)✦ then ℛ\mathcal R and 𝒞\mathcal C have a pruning.

  2. Γ\Gamma has a matching MM whose parts α\alpha and β\beta satisfy |M|=ν(Γ),|α|=ν(Γα),|β|=ν(Γβ).|M| = \nu(\Gamma), \qquad |\alpha| = \nu(\Gamma_\alpha), \qquad |\beta| = \nu(\Gamma_\beta).(6)✦

Let GG be a finite bipartite graph with left side LL and right side RR.

  1. If MM is a maximum matching of GG, then GG has a vertex cover (A,B)(A, B) with |A|+|B|=|M||A| + |B| = |M|(7)✦ in which every vertex of AA and of BB lies on an edge of GG.

  2. If (A,B)(A, B) is a vertex cover of GG of least size, then GG has a matching NN with |N|=|A|+|B|.|N| = |A| + |B|.(8)✦

Let moreover P⊆LP \subseteq L and Q⊆RQ \subseteq R be such that every edge of GG that ends in QQ starts in PP.

  1. If a maximum matching MM of GG satisfies |M∩(P×Q‾)|≤|N∩(P×Q‾)|for every maximum matching N of G,|M \cap (P \times \bar Q)| \le |N \cap (P \times \bar Q)| \quad \text{for every maximum matching } N \text{ of } G,(9)✦ then MQM_Q is a maximum matching of GQG_Q.

  2. GG has a matching MM with |M|=ν(G),|MQ|=ν(GQ),|MP‾|=ν(GP‾).|M| = \nu(G), \qquad |M_Q| = \nu(G_Q), \qquad |M_{\bar P}| = \nu(G_{\bar P}).(10)✦

What Is Checked

The claims are stated over the matchings, maximum matchings and vertex covers of a finite bipartite graph and of its blocks, and over the augmented graph Γ\Gamma of ℛ\mathcal R and 𝒞\mathcal C, defined by (4) from the conflicts and from covering from the left and from the right, with its blocks Γα\Gamma_\alpha and Γβ\Gamma_\beta, the parts α\alpha and β\beta of its matchings, the sets ZZ and HH, the uncovered part (2) and the prunings (3).