Claim 3.2, p. 8 — Inequality (2) is valid for n = 4
ProvedCircletTSP.Facet.claim_3_2circlet-inequalityp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1traveling-salesman-polytope
For we have , and , so Inequality (2) reads . The claim is that every Hamiltonian cycle on four cities satisfies it:
This is the base case of the minimal-counterexample argument for Theorem 3.1.
Formalization Note Hamiltonian cycles are orderings π : Equiv.Perm (Fin 4) with incidence vector MetricTSP.tourVec π.
Preamble
import Mathlib import Definitions.Def_MetricTSP_tour_vector import Definitions.Def_CircletTSP_Facet_Setting
Formal statement
namespace CircletTSP.Facet
/-- Claim 3.2 (p. 8): Inequality (2) is valid for `n = 4`, i.e. every Hamiltonian cycle on
four cities satisfies `t₁ + 0·t₂ ≥ 2`. -/
theorem claim_3_2 (π : Equiv.Perm (Fin 4)) :
(4 : ℝ) - 2 ≤ circletForm 4 (MetricTSP.tourVec π) := by sorry
end CircletTSP.Facet
Source
Gutekunst, Williamson, The Circlet Inequalities, arXiv:2012.12363v1, p. 8, Claim 3.2
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.