Theorem 16.12 — the Gale–Ryser Theorem
ProvedAppliedComb.ManyFaces.gale_ryserLet be a positive integer and let and be partitions of (non-increasing strings of positive integers summing to ). Let be the dual (conjugate) partition of , whose -th entry is the number of rows with . Then there is an zero–one matrix with row sum string and column sum string if and only if in the partial order on :
The theorem characterises the degree sequences of bipartite graphs with prescribed part sizes, and it is the basic existence result for zero–one matrices with prescribed margins.
Formalization Note. Partitions are lists satisfying IsPartition t, the order is Dominates, the dual is dual, and a matrix is M : Matrix (Fin R.length) (Fin C.length) ℕ satisfying IsZeroOneMatrixWithSums R C M. The page defines the dual partition with the misprinted rule "at least ", which gives an increasing string, and its worked example does not sum to . The formalization uses the conjugate partition in non-increasing order, the only reading under which the theorem is true; see the definition dualPartition.
import Mathlib import Definitions.Def_AppliedComb_ManyFaces_partitionDominance import Definitions.Def_AppliedComb_ManyFaces_dualPartition import Definitions.Def_AppliedComb_ManyFaces_zeroOneMatrix
namespace AppliedComb.ManyFaces
/-- Theorem 16.12 (Gale–Ryser; Keller & Trotter, *Applied Combinatorics* (2017 Edition), p. 325).
Let `R` and `C` be partitions of a positive integer `t`. Then there is a zero–one matrix with row
sum string `R` and column sum string `C` if and only if `R^d ≥ C` in the poset `P(t)`, where `R^d`
is the dual (conjugate) partition of `R`. -/
theorem gale_ryser (t : ℕ) (ht : 0 < t) (R C : List ℕ) (hR : IsPartition t R)
(hC : IsPartition t C) :
(∃ M : Matrix (Fin R.length) (Fin C.length) ℕ, IsZeroOneMatrixWithSums R C M) ↔
Dominates (dual R) C := by sorry
end AppliedComb.ManyFaces
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
Setting. Let be a natural number with . Let and be finite lists of natural numbers that are both partitions of . That is, each list:
- is non-increasing;
- has only positive entries;
- has entries summing to .
Conclusion. The following two statements are equivalent.
- (Matrix side.) There exists an matrix with natural-number entries such that:
- every entry is or ;
- row sums to for every ;
- column sums to for every .
- (Dominance side.) The list dominates . Here has length equal to the first entry of , and
"Dominates" means both of the following:
- ;
- for every with ,
Degenerate cases.
- Non-empty lists. Because , both and are non-empty, so the empty-list cases of the matrix and dual definitions (dual length , empty matrices) are excluded.
- No partial sums past . No comparison of partial sums beyond index is required.
- Role of . The integer enters only through the requirement that both lists sum to it.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.