Theorem 3.1, p. 8 — the circlet inequalities are valid
ProvedCircletTSP.Facet.theorem_3_1circlet-inequalityp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1traveling-salesman-polytopevalid-inequality
Let be a positive multiple of , , and for let
Then every Hamiltonian cycle on , with incidence vector and length counts , satisfies
That is, the circlet inequalities are valid.
Tight examples include the cycle , which uses two edges of length and edges of length .
Formalization Note "A feasible TSP input" is read as the incidence vector of a Hamiltonian cycle, the object of the paper's proof; validity on all of follows by linearity and is part of the goal theorem. is added: for the inequality holds trivially but the goal's facet statement fails.
Preamble
import Mathlib import Definitions.Def_MetricTSP_tour_vector import Definitions.Def_CircletTSP_Facet_Setting
Formal statement
namespace CircletTSP.Facet
/-- Theorem 3.1 (p. 8): for `n` divisible by `4`, every Hamiltonian cycle on `n` cities satisfies
Inequality (2), `∑_{i=1}^{d} c_i t_i ≥ n - 2`; the circlet inequalities are valid. -/
theorem theorem_3_1 (n : ℕ) (hn : 0 < n) (h4 : 4 ∣ n) (π : Equiv.Perm (Fin n)) :
(n : ℝ) - 2 ≤ circletForm n (MetricTSP.tourVec π) := by sorry
end CircletTSP.Facet
Source
Gutekunst, Williamson, The Circlet Inequalities, arXiv:2012.12363v1, p. 8, Theorem 3.1, Inequality (2)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.