Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 16.12 — the Gale–Ryser Theorem

Proved
AppliedComb.ManyFaces.gale_ryser

by mikedeng1 · Sep 28, 2026 · Mathlib 0df444a (Lean v4.33.1)

combinatoricsinteger-partitionsmatricesp2o-batch-books5p2o-gran-per-chapterp2o-plan-bookp2o-v1

Let ttt be a positive integer and let R=(r1,…,rm)R = (r_1, \dots, r_m)R=(r1​,…,rm​) and C=(c1,…,cn)C = (c_1, \dots, c_n)C=(c1​,…,cn​) be partitions of ttt (non-increasing strings of positive integers summing to ttt). Let RdR^dRd be the dual (conjugate) partition of RRR, whose jjj-th entry is the number of rows iii with ri≥jr_i \ge jri​≥j. Then there is an m×nm \times nm×n zero–one matrix with row sum string RRR and column sum string CCC if and only if Rd≥CR^d \ge CRd≥C in the partial order on P(t)\mathcal P(t)P(t):

∃ M∈{0,1}m×n: row sums R, column sums C  ⟺  r1≤n  and  ∑i≤j(Rd)i≥∑i≤jci  for j=1,…,r1.\exists\, M \in \{0,1\}^{m \times n}:\ \text{row sums } R,\ \text{column sums } C \iff r_1 \le n \ \text{ and } \ \sum_{i \le j} (R^d)_i \ge \sum_{i \le j} c_i \ \text{ for } j = 1, \dots, r_1.∃M∈{0,1}m×n: row sums R, column sums C⟺r1​≤n  and  i≤j∑​(Rd)i​≥i≤j∑​ci​  for j=1,…,r1​.

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 n+1−jn+1-jn+1−j", which gives an increasing string, and its worked example does not sum to ttt. The formalization uses the conjugate partition in non-increasing order, the only reading under which the theorem is true; see the definition dualPartition.

Preamble
import Mathlib
import Definitions.Def_AppliedComb_ManyFaces_partitionDominance
import Definitions.Def_AppliedComb_ManyFaces_dualPartition
import Definitions.Def_AppliedComb_ManyFaces_zeroOneMatrix
Formal statement
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
Source
Keller & Trotter, Applied Combinatorics (2017 Edition), p. 325, Theorem 16.12
Read-back

What the Lean code literally says, in plain math · claude-opus-5-5

Setting. Let ttt be a natural number with t>0t > 0t>0. Let R=(r1,…,rm)R = (r_1,\dots,r_m)R=(r1​,…,rm​) and C=(c1,…,cn)C = (c_1,\dots,c_n)C=(c1​,…,cn​) be finite lists of natural numbers that are both partitions of ttt. That is, each list:

  • is non-increasing;
  • has only positive entries;
  • has entries summing to ttt.

Conclusion. The following two statements are equivalent.

  • (Matrix side.) There exists an m×nm \times nm×n matrix MMM with natural-number entries such that:
    • every entry is 000 or 111;
    • row aaa sums to rar_ara​ for every a=1,…,ma = 1,\dots,ma=1,…,m;
    • column bbb sums to cbc_bcb​ for every b=1,…,nb = 1,\dots,nb=1,…,n.
  • (Dominance side.) The list RdR^dRd dominates CCC. Here Rd=(w1,…,wr1)R^d = (w_1,\dots,w_{r_1})Rd=(w1​,…,wr1​​) has length equal to the first entry r1r_1r1​ of RRR, and
wj=#{ a∈{1,…,m}:ra≥j }.w_j = \#\{\,a \in \{1,\dots,m\} : r_a \ge j\,\}.wj​=#{a∈{1,…,m}:ra​≥j}.

"Dominates" means both of the following:

  • r1≤nr_1 \le nr1​≤n;
  • for every jjj with 1≤j≤r11 \le j \le r_11≤j≤r1​,
∑k=1jck  ≤  ∑k=1jwk.\sum_{k=1}^{j} c_k \;\le\; \sum_{k=1}^{j} w_k.k=1∑j​ck​≤k=1∑j​wk​.

Degenerate cases.

  • Non-empty lists. Because t>0t > 0t>0, both RRR and CCC are non-empty, so the empty-list cases of the matrix and dual definitions (dual length 000, empty matrices) are excluded.
  • No partial sums past r1r_1r1​. No comparison of partial sums beyond index r1r_1r1​ is required.
  • Role of ttt. The integer ttt enters only through the requirement that both lists sum to it.
Human review
  • Endorsed by Shuze Chen · Oct 2, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 2, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me