Proposition 16.11 — the shape of a covering pair in P(t)
ProvedAppliedComb.ManyFaces.covers_structureLet and be partitions of an integer , ordered by partial sums as in the partial order on , with for and for . If covers in , then and there are integers with such that:
- for ;
- for ;
- ;
- either (a) and , or (b) and ;
- if , then for .
In words: is obtained from by moving a single unit from part to a later part (possibly a new last part of size ), and every part strictly between them equals .
This is the step used in the proof of the Gale–Ryser Theorem 16.12, which walks down a maximal chain from to one cover at a time.
Formalization Note. Partitions are lists satisfying IsPartition t; entry V k is the 1-based entry . 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 with the existence of satisfying items 1–5 exactly as printed. In item 5, is natural-number subtraction, which is exact here because item 3 gives .
import Mathlib import Definitions.Def_AppliedComb_ManyFaces_partitionDominance
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
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
Setting. Let , and let and be finite lists of natural numbers.
- Write for and for . These equal the -th entry (1-based) when length, and otherwise, in particular for .
- " is a partition of " means is non-increasing, all entries are positive, and the entries sum to .
- " dominates " means , and for every the sum of the first entries of is at most the sum of the first entries of .
Hypotheses.
- is a partition of .
- is a partition of .
- covers , meaning:
- and are partitions of ;
- dominates ;
- ;
- every partition of with dominating and dominating equals or .
Conclusion. First, . Second, there exist natural numbers with
such that all five of the following hold:
- for every with ;
- for every with ;
- ;
- one of the following holds:
- (a) and , or
- (b) , , and ;
- if , then for every with , both and .
In (5), the subtraction is natural-number subtraction, truncated at . By (3), , so no truncation occurs.
Degenerate cases. The hypotheses are unsatisfiable whenever no covering pair of partitions of exists, and in those cases the statement holds vacuously.
- . The only partition is the empty list, and "covers" requires .
- . The only partition is .
Since and are past the end of their lists, clause (3) with would read , and clause (4a)/(5) comparisons may involve such default zeros.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.