Proof of Theorem 3.1, p. 12 — t₁ + 2t_d = T₁ + T₂ + ⋯ + T_d
ProvedCircletTSP.Facet.window_countcirclet-inequalitycountingp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a positive multiple of and a Hamiltonian cycle on . Then
where is the number of edges of among , the edges of the window of length or .
Each edge of length lies in exactly one of the windows and each edge of length in exactly two, so rotating the window times counts .
Formalization Note The windows are the 0-based vertices .
Preamble
import Mathlib import Definitions.Def_MetricTSP_tour_vector import Definitions.Def_CircletTSP_Facet_Setting
Formal statement
namespace CircletTSP.Facet
/-- Proof of Theorem 3.1 (p. 12): for a Hamiltonian cycle on `n = 2d` vertices,
`t₁ + 2 t_d = T₁ + T₂ + ⋯ + T_d`, where `T_u` counts the edges of the cycle inside the window
`{u, u + 1, u + d, u + 1 + d}` (the windows `u = 1, …, d` are the 0-based `u = 0, …, d - 1`). -/
theorem window_count (n : ℕ) (hn : 0 < n) (h4 : 4 ∣ n) (π : Equiv.Perm (Fin n)) :
lenCount n 1 (MetricTSP.tourVec π) + 2 * lenCount n (n / 2) (MetricTSP.tourVec π) =
∑ u ∈ Finset.univ.filter (fun u : Fin n => u.val < n / 2), window π u := by sorry
end CircletTSP.Facet
Source
Gutekunst, Williamson, The Circlet Inequalities, arXiv:2012.12363v1, pp. 11–12, proof of Theorem 3.1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.