Proposition 4.3, p. 15 — lengths and costs of the surviving edges after contraction
ProvedCircletTSP.Facet.proposition_4_3circlet-inequalitycontractionp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a positive multiple of , , and use the labels . Let be an edge with , and let be the labels after contraction. Then
Moreover
In particular : every such edge gets cheaper or keeps its cost after the contraction.
This controls the cost of all edges of a Hamiltonian cycle that the contraction of §4 leaves in place.
Formalization Note Labels are natural numbers in (keptLabels n), with ; lengths and costs are integers, so and are not truncated. is added for uniformity (for there are no such labels).
Preamble
import Mathlib import Definitions.Def_MetricTSP_tour_vector import Definitions.Def_CircletTSP_Facet_Setting
Formal statement
namespace CircletTSP.Facet
/-- Proposition 4.3 (p. 15): for an edge `{s, t}` with `s, t ∉ {1, 2, d + 1, d + 2}`
(1-based labels, `d = n / 2`), the contracted length `ℓ'_{s',t'}` equals `ℓ_{s,t}` when
`s, t` lie in the same group `{3, …, d}` or `{d + 3, …, n}` and `ℓ_{s,t} - 2` otherwise; the
contracted cost `c'_{s',t'}` equals `c_{s,t}` or `c_{s,t} - 2` according to the printed cases;
in particular the cost never increases. -/
theorem proposition_4_3 (n : ℕ) (hn : 0 < n) (h4 : 4 ∣ n) (s t : ℕ)
(hs : s ∈ keptLabels n) (ht : t ∈ keptLabels n) (hst : s ≠ t) :
conLen n (relabel n s) (relabel n t) =
(if (3 ≤ s ∧ s ≤ n / 2 ∧ 3 ≤ t ∧ t ≤ n / 2) ∨
(n / 2 + 3 ≤ s ∧ s ≤ n ∧ n / 2 + 3 ≤ t ∧ t ≤ n)
then labLen n s t else labLen n s t - 2) ∧
conCost n (relabel n s) (relabel n t) =
(if ((s ≤ n / 2 ∧ t ≤ n / 2) ∨ (n / 2 + 3 ≤ s ∧ n / 2 + 3 ≤ t)) ∧ s % 2 ≠ t % 2 then
labCost n s t
else if ((s ≤ n / 2 ∧ n / 2 + 3 ≤ t) ∨ (t ≤ n / 2 ∧ n / 2 + 3 ≤ s)) ∧
s % 2 = t % 2 then
labCost n s t
else labCost n s t - 2) ∧
conCost n (relabel n s) (relabel n t) ≤ labCost n s t := by sorry
end CircletTSP.Facet
Source
Gutekunst, Williamson, The Circlet Inequalities, arXiv:2012.12363v1, p. 15, Proposition 4.3
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.