Proposition 4.4, p. 17 — the first contraction lowers the cost by at least 4 (inequality (5))
ProvedCircletTSP.Facet.proposition_4_4circlet-inequalitycontractionp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a positive multiple of , , labels . Let be labels outside , and consider contracting the five edges into the single edge . Then
Together with Proposition 4.3 this shows that a Hamiltonian cycle containing this edge sequence (structure B2 at ) contracts to a Hamiltonian cycle on vertices that is at least cheaper.
Formalization Note and are integers; the inequality is in . The sentence "Hence the cost of the tour … goes down by at least 4" is the separate item contraction_step.
Preamble
import Mathlib import Definitions.Def_MetricTSP_tour_vector import Definitions.Def_CircletTSP_Facet_Setting
Formal statement
namespace CircletTSP.Facet
/-- Proposition 4.4 (p. 17), inequality (5): contracting `{j, 1}, {1, 2}, {2, d + 2},
{d + 2, d + 1}, {d + 1, k}` into `{j', k'}` lowers the cost by at least `4`
(1-based labels, `d = n / 2`, `j ≠ k` outside `{1, 2, d + 1, d + 2}`). -/
theorem proposition_4_4 (n : ℕ) (hn : 0 < n) (h4 : 4 ∣ n) (j k : ℕ)
(hj : j ∈ keptLabels n) (hk : k ∈ keptLabels n) (hjk : j ≠ k) :
labCost n j 1 + labCost n 1 2 + labCost n 2 (n / 2 + 2) + labCost n (n / 2 + 2) (n / 2 + 1) +
labCost n (n / 2 + 1) k - conCost n (relabel n j) (relabel n k) ≥ 4 := by sorry
end CircletTSP.Facet
Source
Gutekunst, Williamson, The Circlet Inequalities, arXiv:2012.12363v1, p. 17, Proposition 4.4, inequality (5)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.