Proposition 4.5, p. 17 — the second contraction saves an even amount ≥ 2 (inequality (6)), and another edge drops when it is 2
ProvedCircletTSP.Facet.proposition_4_5circlet-inequalitycontractionp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a positive multiple of , , labels . Let be labels outside , and consider contracting into . Write
Then:
- (inequality (6)) and is even;
- if , then every Hamiltonian cycle on containing these five edges also contains an edge with and .
In either case the contracted Hamiltonian cycle (structure A at ) is at least cheaper than the original.
Formalization Note Costs are integers. The cycle is an ordering π : Equiv.Perm (Fin n); "contains the edge " refers to the vertices with labels (vertex v has label ). The concluding sentence "In either case …" 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.5 (p. 17): contracting `{j, d + 2}, {d + 2, 2}, {2, 1}, {1, d + 1}, {d + 1, k}`
into `{j', k'}` lowers the cost of these edges by an even amount that is at least `2` (inequality
(6)); and if it is exactly `2`, then every Hamiltonian cycle containing these five edges has
another edge `{s, t}` with `s, t ∉ {1, 2, d + 1, d + 2}` whose cost drops by `2`
(1-based labels, `d = n / 2`). -/
theorem proposition_4_5 (n : ℕ) (hn : 0 < n) (h4 : 4 ∣ n) (j k : ℕ)
(hj : j ∈ keptLabels n) (hk : k ∈ keptLabels n) (hjk : j ≠ k) :
2 ≤ labCost n j (n / 2 + 2) + labCost n (n / 2 + 2) 2 + labCost n 2 1 +
labCost n 1 (n / 2 + 1) + labCost n (n / 2 + 1) k - conCost n (relabel n j) (relabel n k) ∧
Even (labCost n j (n / 2 + 2) + labCost n (n / 2 + 2) 2 + labCost n 2 1 +
labCost n 1 (n / 2 + 1) + labCost n (n / 2 + 1) k -
conCost n (relabel n j) (relabel n k)) ∧
∀ π : Equiv.Perm (Fin n), ChainTwo π j k →
labCost n j (n / 2 + 2) + labCost n (n / 2 + 2) 2 + labCost n 2 1 +
labCost n 1 (n / 2 + 1) + labCost n (n / 2 + 1) k -
conCost n (relabel n j) (relabel n k) = 2 →
∃ s ∈ keptLabels n, ∃ t ∈ keptLabels n, HasEdge π s t ∧
conCost n (relabel n s) (relabel n t) = labCost n s t - 2 := by sorry
end CircletTSP.Facet
Source
Gutekunst, Williamson, The Circlet Inequalities, arXiv:2012.12363v1, p. 17, Proposition 4.5, inequality (6)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.