Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proposition 2.1 — convex hull via LP min–max for integer objectives

Proved
ChvatalPolytopes.Perfect.convexHull_iff_minmax

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

convex-hulllp-dualityp2o-batch-p100ap2o-gran-per-chapterp2o-plan-paperp2o-v1polyhedral-combinatorics

Let VVV and JJJ be finite index sets, aiua_{iu}aiu​ and bib_ibi​ (i∈Ji\in Ji∈J, u∈Vu\in Vu∈V) real numbers, and consider the linear system

−xu≤0(u∈V),∑u∈Vaiuxu≤bi(i∈J).(2.1)-x_u\le 0\quad(u\in V),\qquad \sum_{u\in V}a_{iu}x_u\le b_i\quad(i\in J).\tag{2.1}−xu​≤0(u∈V),u∈V∑​aiu​xu​≤bi​(i∈J).(2.1)

Let SSS be a finite nonempty set of solutions of (2.1). Then the set of all solutions of (2.1) is the convex hull of SSS if and only if, for every integer-valued vector c=(cu:u∈V)c=(c_u:u\in V)c=(cu​:u∈V),

max⁡{cx:x∈S}=min⁡{∑i∈Jλibi  :  λi≥0 for all i∈J, ∑i∈Jλiaiu≥cu for all u∈V}.\max\{cx : x\in S\}=\min\Big\{\sum_{i\in J}\lambda_ib_i \;:\; \lambda_i\ge0 \text{ for all } i\in J,\ \sum_{i\in J}\lambda_ia_{iu}\ge c_u \text{ for all } u\in V\Big\}.max{cx:x∈S}=min{i∈J∑​λi​bi​:λi​≥0 for all i∈J, i∈J∑​λi​aiu​≥cu​ for all u∈V}.

The proposition turns the polyhedral statement "(2.1) is a defining linear system of conv⁡S\operatorname{conv}SconvS" into a family of min–max equalities, one for each integral objective. It is the bridge between Theorem 3.1(i) and the combinatorial condition used in its proof.

Formalization Note "min = max" is stated as two clauses: every feasible λ≥0\lambda\ge0λ≥0 has ∑iλibi≥max⁡x∈Scx\sum_i\lambda_ib_i\ge\max_{x\in S}cx∑i​λi​bi​≥maxx∈S​cx, and some feasible λ≥0\lambda\ge0λ≥0 attains equality. The hypothesis that SSS is nonempty is added (the paper's max⁡{cx:x∈S}\max\{cx:x\in S\}max{cx:x∈S} requires it). The nonnegativity rows −xu≤0-x_u\le0−xu​≤0 are kept, as a separate conjunct x≥0x\ge0x≥0 of the solution set; without them the statement is false. JJJ is a finite type and a,ba,ba,b are real; ccc ranges over ZV\mathbb Z^VZV.

Preamble
import Mathlib
Formal statement
namespace ChvatalPolytopes.Perfect

/-- **Proposition 2.1** (Chvátal 1975, pp. 139–140). Let `S` be a finite set of solutions
`x = (x_u : u ∈ V)` of the system (2.1)
`−x_u ≤ 0 (u ∈ V)`, `Σ (a_{iu} x_u : u ∈ V) ≤ b_i (i ∈ J)`.
Then the set of all solutions of (2.1) is the convex hull of `S` if and only if, for every
integer-valued vector `c = (c_u : u ∈ V)`,
`max {cx : x ∈ S} = min {Σ (λ_i b_i : i ∈ J) : λ_i ≥ 0 for all i ∈ J and
Σ (λ_i a_{iu} : i ∈ J) ≥ c_u for all u ∈ V}`.

"min = max" is stated as: (a) every feasible `λ` has objective `≥ max_{x ∈ S} cx`, and (b) some
feasible `λ` has objective equal to it. The hypothesis `S.Nonempty` is added (the paper's
`max {cx : x ∈ S}` requires it). The nonnegativity rows `−x_u ≤ 0` are kept as the conjunct
`∀ u, 0 ≤ x u`; `J` is a finite index type and the coefficients `a`, `b` are real. -/
theorem convexHull_iff_minmax {V : Type*} [Fintype V] {J : Type*} [Fintype J]
    (a : J → V → ℝ) (b : J → ℝ) (S : Finset (V → ℝ)) (hS : S.Nonempty)
    (hSsol : ∀ x ∈ S, (∀ u, 0 ≤ x u) ∧ ∀ i, ∑ u, a i u * x u ≤ b i) :
    {x : V → ℝ | (∀ u, 0 ≤ x u) ∧ ∀ i, ∑ u, a i u * x u ≤ b i} = convexHull ℝ (S : Set (V → ℝ)) ↔
      ∀ c : V → ℤ,
        (∀ lam : J → ℝ, (∀ i, 0 ≤ lam i) → (∀ u, (c u : ℝ) ≤ ∑ i, lam i * a i u) →
          S.sup' hS (fun x => ∑ u, (c u : ℝ) * x u) ≤ ∑ i, lam i * b i) ∧
        (∃ lam : J → ℝ, (∀ i, 0 ≤ lam i) ∧ (∀ u, (c u : ℝ) ≤ ∑ i, lam i * a i u) ∧
          ∑ i, lam i * b i = S.sup' hS (fun x => ∑ u, (c u : ℝ) * x u)) := by sorry

end ChvatalPolytopes.Perfect
Source
Chvátal, On certain polytopes associated with graphs, J. Combin. Theory Ser. B 18 (1975), pp. 139–140, Proposition 2.1
Read-back

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

Data and hypotheses.

  • VVV and JJJ are finite index sets.
  • a=(aiu)i∈J, u∈Va = (a_{iu})_{i \in J,\, u \in V}a=(aiu​)i∈J,u∈V​ is a real matrix and b=(bi)i∈Jb = (b_i)_{i \in J}b=(bi​)i∈J​ is a real vector.
  • S⊆RVS \subseteq \mathbb{R}^VS⊆RV is a nonempty finite set of vectors.
  • Every x∈Sx \in Sx∈S solves the system
xu≥0 (u∈V),∑u∈Vaiuxu≤bi (i∈J).x_u \ge 0 \ (u \in V), \qquad \sum_{u \in V} a_{iu} x_u \le b_i \ (i \in J).xu​≥0 (u∈V),u∈V∑​aiu​xu​≤bi​ (i∈J).

Let PPP be the set of all real solutions of this system.

Claim. P=conv⁡(S)P = \operatorname{conv}(S)P=conv(S) if and only if the following holds for every integer vector c∈ZVc \in \mathbb{Z}^Vc∈ZV. Write

Mc=max⁡x∈S∑u∈Vcuxu,M_c = \max_{x \in S} \sum_{u \in V} c_u x_u,Mc​=x∈Smax​u∈V∑​cu​xu​,

which is a genuine maximum because SSS is finite and nonempty. Call λ∈RJ\lambda \in \mathbb{R}^Jλ∈RJ dual feasible if

λi≥0  (i∈J),cu≤∑i∈Jλiaiu  (u∈V).\lambda_i \ge 0 \ \ (i \in J), \qquad c_u \le \sum_{i \in J} \lambda_i a_{iu} \ \ (u \in V).λi​≥0  (i∈J),cu​≤i∈J∑​λi​aiu​  (u∈V).

Then both of the following must hold:

  • (a) every dual-feasible λ\lambdaλ satisfies ∑i∈Jλibi≥Mc\sum_{i \in J} \lambda_i b_i \ge M_c∑i∈J​λi​bi​≥Mc​;
  • (b) some dual-feasible λ\lambdaλ satisfies ∑i∈Jλibi=Mc\sum_{i \in J} \lambda_i b_i = M_c∑i∈J​λi​bi​=Mc​.

Degenerate cases.

  • The maximum McM_cMc​ involves no default values, because SSS is required to be nonempty.
  • If JJJ is empty, PPP is the nonnegative orthant. Dual feasibility then reduces to cu≤0c_u \le 0cu​≤0 for all uuu, with dual objective 000. For any ccc with a positive entry, no dual-feasible λ\lambdaλ exists and (b) fails.
  • If VVV is empty, RV\mathbb{R}^VRV is a single point and SSS is that point. ccc is the empty vector, Mc=0M_c = 0Mc​=0, and λ=0\lambda = 0λ=0 is dual feasible with objective 000.
  • The statement quantifies only over integer ccc, not real ccc.
Human review
  • Endorsed by Shuze Chen · Sep 27, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Sep 27, 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