Theorem 5.1, p. 20 — for 4 ∣ n the circlet inequality is valid for STSP(n) and defines a facet of it
ProvedCircletTSP.Facet.theorem_5_1Let be a positive multiple of and . The circlet inequality
is facet defining for the symmetric traveling salesman polytope :
- it is valid: every satisfies it;
- the face is a facet of , i.e. a nonempty face with .
This is the main result of the paper: the circlet inequality, whose coefficients depend only on edge lengths around a circle (a circulant inequality), is not merely valid but one of the inequalities in any minimal linear description of .
Formalization Note is the convex hull of the incidence vectors MetricTSP.tourVec π, in ordered-pair coordinates. "Facet" is the published Disjunctive.Polarity.IsFacet: an extreme subset, nonempty, of affine dimension one less than . Validity is conjoined explicitly, since IsFacet alone would also hold for the reversed inequality. is added: , but is a single point and the facet claim fails there.
import Mathlib import Definitions.Def_Disjunctive_Polarity_Projection import Definitions.Def_CircletTSP_Facet_Setting
namespace CircletTSP.Facet
/-- Theorem 5.1 (p. 20): for `4 ∣ n`, the circlet inequality `∑_{i=1}^{d} c_i t_i ≥ n - 2` is
facet defining for `STSP(n)`: it is valid on `STSP(n)`, and the points of `STSP(n)` where it
holds with equality form a facet of `STSP(n)`. -/
theorem theorem_5_1 (n : ℕ) (hn : 0 < n) (h4 : 4 ∣ n) :
(∀ x ∈ STSP n, (n : ℝ) - 2 ≤ circletForm n x) ∧
Disjunctive.Polarity.IsFacet (STSP n) (STSP n ∩ {x | circletForm n x = (n : ℝ) - 2}) := by sorry
end CircletTSP.Facet
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.