Lemma 4 (Hoffman–Kruskal), p. 23, corrected: for A totally unimodular and b integral, every vertex of {λ : Aλ = b, −1 ≤ λ ≤ 1} is integral
ProvedProConChoice.Rational.lemma_4Let be a real matrix with rows indexed by a finite set and columns by a finite set , and let . Consider the polytope
If is totally unimodular and has integer entries, then every vertex (extreme point) of has integer coordinates.
In Section 7 this is applied to the system (RS)–(CS), whose right-hand side consists of the integer weights of the previous step and the integer Möbius transforms of a deterministic choice function.
Formalization Note Corrected statement. The paper's Lemma 4 omits the hypothesis that is integral; without it the lemma is false (, : the only vertex is ). In Section 7, where the lemma is applied, is integral. Vertices are the extreme points of (Set.extremePoints ℝ Q), and integer valued means every coordinate equals some integer.
import Mathlib
namespace ProConChoice.Rational
/-- Lemma 4 (Hoffman–Kruskal, p. 23; corrected: `b` integral, as it is in Section 7): if `A` is
totally unimodular and `b` is integral, every vertex (extreme point) of
`Q = {λ : Aλ = b, -1 ≤ λ ≤ 1}` has integer coordinates. -/
theorem lemma_4 {m n : Type*} [Fintype m] [Fintype n]
(A : Matrix m n ℝ) (hA : A.IsTotallyUnimodular) (b : m → ℝ) (hb : ∀ i, ∃ z : ℤ, b i = z) :
∀ v ∈ Set.extremePoints ℝ {x : n → ℝ | A.mulVec x = b ∧ ∀ j, -1 ≤ x j ∧ x j ≤ 1},
∀ j, ∃ z : ℤ, v j = z := by sorry
end ProConChoice.Rational
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.