Lemma 3.3, pp. 9–10 — a tour violating Inequality (2) has t₁ + 2t_d > n + 2
ProvedCircletTSP.Facet.lemma_3_3circlet-inequalityp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1traveling-salesman-polytope
Let be a positive multiple of and . Let be a Hamiltonian cycle on with incidence vector such that
Then
A counterexample to validity must therefore use many cheap edges, those of length and . By Theorem 3.1 no Hamiltonian cycle satisfies the hypothesis; the lemma is a step of the paper's minimal-counterexample proof and is stated exactly as printed.
Formalization Note "A valid TSP instance" is read as a Hamiltonian cycle, given by an ordering π; is added (the paper's with even is tacitly positive).
Preamble
import Mathlib import Definitions.Def_MetricTSP_tour_vector import Definitions.Def_CircletTSP_Facet_Setting
Formal statement
namespace CircletTSP.Facet
/-- Lemma 3.3 (pp. 9–10): a Hamiltonian cycle violating Inequality (2) satisfies
`t₁ + 2 t_d > n + 2`, where `d = n / 2`. -/
theorem lemma_3_3 (n : ℕ) (hn : 0 < n) (h4 : 4 ∣ n) (π : Equiv.Perm (Fin n))
(hlt : circletForm n (MetricTSP.tourVec π) < (n : ℝ) - 2) :
lenCount n 1 (MetricTSP.tourVec π) + 2 * lenCount n (n / 2) (MetricTSP.tourVec π) >
(n : ℝ) + 2 := by sorry
end CircletTSP.Facet
Source
Gutekunst, Williamson, The Circlet Inequalities, arXiv:2012.12363v1, pp. 9–10, Lemma 3.3
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.