Proof of Lemma 3, p. 11 — linear extensions equal factorial times order-polytope volume
ProvedSPHardness.OrderPolytope.numLinExt_eqcombinatoricslinear-extensionsorder-polytopep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1volume
Let be a finite poset with , let be its number of linear extensions, and let be the volume of its order polytope. The identity cited in the proof of Lemma 3 is
This is the geometric bridge between the counting problem and volume approximation. The identity is a theorem to be proved, rather than an assumption in the reduction.
Formalization Note Linear extensions use the published FCP.Order.LinearExtensions definition: order-preserving bijections from to the positions .
Preamble
import Mathlib import Definitions.Def_SPHardness_OrderPolytope_Model
Formal statement
namespace SPHardness.OrderPolytope
open scoped Nat
/-- The Brightwell–Winkler linear-extension/volume identity quoted in Lemma 3. -/
theorem numLinExt_eq (P : Type) [Fintype P] [PartialOrder P] :
(numLinExt P : ℝ) = ((Fintype.card P)! : ℝ) * volOrder P := by sorry
end SPHardness.OrderPolytope
Source
Hanasusanto, Kuhn & Wiesemann, A comment on "computational complexity of stochastic programming problems", Optimization Online preprint 2015/03/4825 (version of October 6, 2015), p. 11, proof of Lemma 3, citing Brightwell & Winkler [3]. https://optimization-online.org/wp-content/uploads/2015/03/4825.pdf
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.