Proof of Theorem 3.1, p. 12 — without the structures of Figure 4 every window has T_u ≤ 2
ProvedCircletTSP.Facet.window_le_twocirclet-inequalitycountingp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a multiple of , , and let be a Hamiltonian cycle on that contains none of the structures A, B1, B2 of Figure 4 at any vertex. Then for every vertex ,
would make the window a subtour, and means three edges of the window's -cycle, which form one of the structures of Figure 4. Combined with the window count and Lemma 3.4 this gives , contradicting Lemma 3.3.
Formalization Note The hypothesis "no structure at any vertex" is what Lemma 3.4 supplies ("for any "); it is needed in this form, since three window edges at may form structure A at rather than a structure at . is the page's "By Claim 3.2, " (p. 10).
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): in a Hamiltonian cycle on `n ≥ 8` vertices containing none of
the structures A, B1, B2 of Figure 4 (at any vertex), every window count satisfies `T_u ≤ 2`. -/
theorem window_le_two (n : ℕ) (hn : 8 ≤ n) (h4 : 4 ∣ n) (π : Equiv.Perm (Fin n))
(hno : ∀ u : Fin n, ¬ IsStructA π u ∧ ¬ IsStructB1 π u ∧ ¬ IsStructB2 π u) :
∀ u : Fin n, window π u ≤ 2 := by sorry
end CircletTSP.Facet
Source
Gutekunst, Williamson, The Circlet Inequalities, arXiv:2012.12363v1, p. 12, proof of Theorem 3.1 ('By Lemma 3.4, T_u ≤ 2')
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.