Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proposition 16.11 — the shape of a covering pair in P(t)

Proved
AppliedComb.ManyFaces.covers_structure

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

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

Let V=(v1,…,vm)V = (v_1, \dots, v_m)V=(v1​,…,vm​) and W=(w1,…,wn)W = (w_1, \dots, w_n)W=(w1​,…,wn​) be partitions of an integer ttt, ordered by partial sums as in the partial order on P(t)\mathcal P(t)P(t), with vk=0v_k = 0vk​=0 for k>mk > mk>m and wk=0w_k = 0wk​=0 for k>nk > nk>n. If VVV covers WWW in P(t)\mathcal P(t)P(t), then n≤m+1n \le m + 1n≤m+1 and there are integers i,ji, ji,j with 1≤i<j≤n1 \le i < j \le n1≤i<j≤n such that:

  1. vα=wαv_\alpha = w_\alphavα​=wα​ for 1≤α<i1 \le \alpha < i1≤α<i;
  2. vβ=wβv_\beta = w_\betavβ​=wβ​ for j<β≤mj < \beta \le mj<β≤m;
  3. vi=1+wiv_i = 1 + w_ivi​=1+wi​;
  4. either (a) j≤mj \le mj≤m and wj=1+vjw_j = 1 + v_jwj​=1+vj​, or (b) j=n=m+1j = n = m + 1j=n=m+1 and wj=1w_j = 1wj​=1;
  5. if j>i+1j > i + 1j>i+1, then wγ=vγ=vi−1w_\gamma = v_\gamma = v_i - 1wγ​=vγ​=vi​−1 for i<γ<ji < \gamma < ji<γ<j.

In words: WWW is obtained from VVV by moving a single unit from part iii to a later part jjj (possibly a new last part of size 111), and every part strictly between them equals vi−1v_i - 1vi​−1.

W=(v1,…,vi−1,  vi−1,  vi+1,…,vj−1,  vj+1,  vj+1,… ).W = (v_1, \dots, v_{i-1},\; v_i - 1,\; v_{i+1}, \dots, v_{j-1},\; v_j + 1,\; v_{j+1}, \dots).W=(v1​,…,vi−1​,vi​−1,vi+1​,…,vj−1​,vj​+1,vj+1​,…).

This is the step used in the proof of the Gale–Ryser Theorem 16.12, which walks down a maximal chain from RdR^dRd to CCC one cover at a time.

Formalization Note. Partitions are lists satisfying IsPartition t; entry V k is the 1-based entry vkv_kvk​. The hypotheses IsPartition t V and IsPartition t W repeat what Covers t V W already contains, as the book states them separately. The conclusion is the conjunction of n≤m+1n \le m+1n≤m+1 with the existence of i,ji, ji,j satisfying items 1–5 exactly as printed. In item 5, vi−1v_i - 1vi​−1 is natural-number subtraction, which is exact here because item 3 gives vi≥1v_i \ge 1vi​≥1.

Preamble
import Mathlib
import Definitions.Def_AppliedComb_ManyFaces_partitionDominance
Formal statement
namespace AppliedComb.ManyFaces

/-- Proposition 16.11 (Keller & Trotter, *Applied Combinatorics* (2017 Edition), p. 324).
Let `V = (v_1, …, v_m)` and `W = (w_1, …, w_n)` be partitions of `t`. If `V` covers `W` in `P(t)`,
then `n ≤ m + 1` and there are integers `1 ≤ i < j ≤ n` such that
1. `v_α = w_α` for `1 ≤ α < i`;
2. `v_β = w_β` for `j < β ≤ m`;
3. `v_i = 1 + w_i`;
4. either (a) `j ≤ m` and `w_j = 1 + v_j`, or (b) `j = n = m + 1` and `w_j = 1`;
5. if `j > i + 1`, then `w_γ = v_γ = v_i − 1` for `i < γ < j`.
Entries are 1-based (`entry V k = v_k`). -/
theorem covers_structure (t : ℕ) (V W : List ℕ) (hV : IsPartition t V) (hW : IsPartition t W)
    (hcov : Covers t V W) :
    W.length ≤ V.length + 1 ∧
      ∃ i j : ℕ, 1 ≤ i ∧ i < j ∧ j ≤ W.length ∧
        (∀ α : ℕ, 1 ≤ α → α < i → entry V α = entry W α) ∧
        (∀ β : ℕ, j < β → β ≤ V.length → entry V β = entry W β) ∧
        entry V i = 1 + entry W i ∧
        ((j ≤ V.length ∧ entry W j = 1 + entry V j) ∨
          (j = W.length ∧ W.length = V.length + 1 ∧ entry W j = 1)) ∧
        (i + 1 < j → ∀ γ : ℕ, i < γ → γ < j →
          entry W γ = entry V γ ∧ entry V γ = entry V i - 1) := by sorry

end AppliedComb.ManyFaces
Source
Keller & Trotter, Applied Combinatorics (2017 Edition), p. 324, Proposition 16.11
Read-back

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

Setting. Let t∈Nt \in \mathbb Nt∈N, and let V=(v1,…,vm)V = (v_1,\dots,v_m)V=(v1​,…,vm​) and W=(w1,…,wn)W = (w_1,\dots,w_n)W=(w1​,…,wn​) be finite lists of natural numbers.

  • Write vkv_kvk​ for entry(V,k)\mathrm{entry}(V,k)entry(V,k) and wkw_kwk​ for entry(W,k)\mathrm{entry}(W,k)entry(W,k). These equal the kkk-th entry (1-based) when 1≤k≤1 \le k \le1≤k≤ length, and 000 otherwise, in particular vk=0v_k = 0vk​=0 for k>mk > mk>m.
  • "XXX is a partition of ttt" means XXX is non-increasing, all entries are positive, and the entries sum to ttt.
  • "XXX dominates YYY" means ∣X∣≤∣Y∣|X| \le |Y|∣X∣≤∣Y∣, and for every 1≤j≤∣X∣1 \le j \le |X|1≤j≤∣X∣ the sum of the first jjj entries of YYY is at most the sum of the first jjj entries of XXX.

Hypotheses.

  1. VVV is a partition of ttt.
  2. WWW is a partition of ttt.
  3. VVV covers WWW, meaning:
    • VVV and WWW are partitions of ttt;
    • VVV dominates WWW;
    • V≠WV \ne WV=W;
    • every partition UUU of ttt with VVV dominating UUU and UUU dominating WWW equals VVV or WWW.

Conclusion. First, n≤m+1n \le m + 1n≤m+1. Second, there exist natural numbers i,ji, ji,j with

1≤i<j≤n1 \le i < j \le n1≤i<j≤n

such that all five of the following hold:

  1. vα=wαv_\alpha = w_\alphavα​=wα​ for every α\alphaα with 1≤α<i1 \le \alpha < i1≤α<i;
  2. vβ=wβv_\beta = w_\betavβ​=wβ​ for every β\betaβ with j<β≤mj < \beta \le mj<β≤m;
  3. vi=1+wiv_i = 1 + w_ivi​=1+wi​;
  4. one of the following holds:
    • (a) j≤mj \le mj≤m and wj=1+vjw_j = 1 + v_jwj​=1+vj​, or
    • (b) j=nj = nj=n, n=m+1n = m + 1n=m+1, and wj=1w_j = 1wj​=1;
  5. if i+1<ji + 1 < ji+1<j, then for every γ\gammaγ with i<γ<ji < \gamma < ji<γ<j, both wγ=vγw_\gamma = v_\gammawγ​=vγ​ and vγ=vi−1v_\gamma = v_i - 1vγ​=vi​−1.

In (5), the subtraction is natural-number subtraction, truncated at 000. By (3), vi≥1v_i \ge 1vi​≥1, so no truncation occurs.

Degenerate cases. The hypotheses are unsatisfiable whenever no covering pair of partitions of ttt exists, and in those cases the statement holds vacuously.

  • t=0t = 0t=0. The only partition is the empty list, and "covers" requires V≠WV \ne WV=W.
  • t=1t = 1t=1. The only partition is (1)(1)(1).

Since vkv_kvk​ and wkw_kwk​ are 000 past the end of their lists, clause (3) with i>mi > mi>m would read 0=1+wi0 = 1 + w_i0=1+wi​, and clause (4a)/(5) comparisons may involve such default zeros.

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