Lemma 3.4, p. 10 — a minimal counterexample has none of the structures of Figure 4
ProvedCircletTSP.Facet.lemma_3_4circlet-inequalityp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1traveling-salesman-polytope
Let be a positive multiple of and . Let be a Hamiltonian cycle on with
and suppose it is minimal with respect to : for every with and , every Hamiltonian cycle on satisfies Inequality (2) for . Then for every vertex , contains none of the three edge sets
(structures A, B1, B2 of Figure 4; labels mod ).
This is the technical lemma behind Theorem 3.1. Its hypotheses cannot hold once Theorem 3.1 is known; it is stated as printed.
Formalization Note "Minimal with respect to " quantifies over smaller multiples of only, as in the paper's induction on .
Preamble
import Mathlib import Definitions.Def_MetricTSP_tour_vector import Definitions.Def_CircletTSP_Facet_Setting
Formal statement
namespace CircletTSP.Facet
/-- Lemma 3.4 (p. 10): a Hamiltonian cycle violating Inequality (2) on a number of vertices `n`
that is minimal (every Hamiltonian cycle on `m` vertices, `0 < m < n`, `4 ∣ m`, satisfies
Inequality (2)) contains none of the structures A, B1, B2 of Figure 4, at any vertex `u`. -/
theorem lemma_3_4 (n : ℕ) (hn : 0 < n) (h4 : 4 ∣ n) (π : Equiv.Perm (Fin n))
(hlt : circletForm n (MetricTSP.tourVec π) < (n : ℝ) - 2)
(hmin : ∀ m : ℕ, 0 < m → m < n → 4 ∣ m → ∀ σ : Equiv.Perm (Fin m),
(m : ℝ) - 2 ≤ circletForm m (MetricTSP.tourVec σ)) :
∀ u : Fin n, ¬ IsStructA π u ∧ ¬ IsStructB1 π u ∧ ¬ IsStructB2 π u := by sorry
end CircletTSP.Facet
Source
Gutekunst, Williamson, The Circlet Inequalities, arXiv:2012.12363v1, p. 10, Lemma 3.4
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.