Theorem 6.5 — Frank's discrete separation theorem for a submodular/supermodular pair
ProvedSteinitzExchange.Duality.frank_discrete_separationdiscrete-separationintegralityp2o-batch-p100bp2o-gran-per-chapterp2o-plan-paperp2o-v1submodular-function
Let be submodular and supermodular with . If for all , then there exists such that
Moreover, if and are integer-valued, there exists such an in .
This is Frank's discrete separation theorem (1982), stated in the paper with a citation and no proof. In the duality theorem it yields a common point of and whenever the dual problem is bounded.
Preamble
import Mathlib import Definitions.Def_SteinitzExchange_Duality_IntegralBaseSet import Definitions.Def_SteinitzExchange_Duality_SetFunction
Formal statement
namespace SteinitzExchange.Duality
/-- Murota 1996, p. 296, Theorem 6.5 (Frank's discrete separation theorem [14]). Let
`f : 2^V → ℝ` be submodular and `g : 2^V → ℝ` supermodular with `f(∅) = g(∅) = 0`. If
`g(X) ≤ f(X)` for all `X ⊆ V`, there is `x* ∈ ℝ^V` with `g(X) ≤ x*(X) ≤ f(X)` for all `X ⊆ V`
(Eq. (6.6)). Moreover, if `f` and `g` are integer-valued, such an `x*` exists in `ℤ^V`. -/
theorem frank_discrete_separation {V : Type*} [Fintype V] [DecidableEq V] [Nonempty V]
(f g : Finset V → ℝ) (hf : IsSubmodular f) (hg : IsSupermodular g)
(hf0 : f ∅ = 0) (hg0 : g ∅ = 0) (hgf : ∀ X : Finset V, g X ≤ f X) :
(∃ xs : V → ℝ, ∀ X : Finset V, g X ≤ ∑ v ∈ X, xs v ∧ ∑ v ∈ X, xs v ≤ f X) ∧
((∀ X : Finset V, ∃ k : ℤ, f X = k) → (∀ X : Finset V, ∃ k : ℤ, g X = k) →
∃ xs : V → ℤ, ∀ X : Finset V,
g X ≤ ((sumOn xs X : ℤ) : ℝ) ∧ ((sumOn xs X : ℤ) : ℝ) ≤ f X) := by sorry
end SteinitzExchange.Duality
Source
Murota, Convexity and Steinitz's Exchange Property, Adv. Math. 124 (1996), p. 296, Theorem 6.5 (citing [14] = A. Frank, An algorithm for submodular functions on graphs, Ann. Discrete Math. 16 (1982) 97-120)
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
Setting.
- is a finite, nonempty type with decidable equality.
- are functions on all subsets of .
Hypotheses.
- is submodular: for all .
- is supermodular: for all .
- .
- for every .
Claim.
- There is a real vector such that for every :
- If additionally every value and every value is an integer, then there is an integer vector with the same two-sided bound for every .
Degenerate cases. For the bound reads . No equality is assumed or asserted. If has a single element , the claim reduces to the existence of a real (respectively integer) number between and . Empty is excluded by hypothesis.
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.