Claim 4.2, p. 13 — rotation moves a structure A or B2 to u = 1 at equal circlet cost
ProvedCircletTSP.Facet.claim_4_2circlet-inequalityp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1symmetry
Let be a positive multiple of and a Hamiltonian cycle on . If contains structure A (resp. B2) of Figure 4 at some vertex , then there is a Hamiltonian cycle with the same value of containing structure A (resp. B2) at .
Hence a counterexample to Theorem 3.1 with an instance of A or B2 may be assumed to have it at , which is Claim 4.2 ("without loss of generality, we may assume that ").
Formalization Note Stated in the form the proof gives (relabelling preserves every length), which implies the printed claim about counterexamples. The paper's vertex is the 0-based vertex .
Preamble
import Mathlib import Definitions.Def_MetricTSP_tour_vector import Definitions.Def_CircletTSP_Facet_Setting
Formal statement
namespace CircletTSP.Facet
/-- Claim 4.2 (p. 13), in the form its proof gives: a Hamiltonian cycle containing structure A
(resp. B2) of Figure 4 at some `u` can be relabelled into one of the same circlet cost containing
the same structure at `u = 1` (the vertex `0` in 0-based labels). -/
theorem claim_4_2 (n : ℕ) (hn : 0 < n) (h4 : 4 ∣ n) (π : Equiv.Perm (Fin n)) (u : Fin n) :
(IsStructA π u → ∃ π' : Equiv.Perm (Fin n),
circletForm n (MetricTSP.tourVec π') = circletForm n (MetricTSP.tourVec π) ∧
IsStructA π' ⟨0, hn⟩) ∧
(IsStructB2 π u → ∃ π' : Equiv.Perm (Fin n),
circletForm n (MetricTSP.tourVec π') = circletForm n (MetricTSP.tourVec π) ∧
IsStructB2 π' ⟨0, hn⟩) := by sorry
end CircletTSP.Facet
Source
Gutekunst, Williamson, The Circlet Inequalities, arXiv:2012.12363v1, p. 13, Claim 4.2 and its proof
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.