p. 19 (Naddef–Rinaldi, Theorem 3.7) — dim STSP(n) = |E| − |V| = n(n − 3)/2
ProvedCircletTSP.Facet.stsp_dimp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1polytope-dimensiontraveling-salesman-polytope
For , the symmetric traveling salesman polytope has dimension
The paper cites this from Naddef and Rinaldi (Theorem 3.7) to reduce the facet property of a valid inequality to exhibiting tight Hamiltonian cycles with linearly independent incidence vectors.
Formalization Note The dimension is that of the affine hull (Disjunctive.Polarity.PolyDim, the finrank of the vector span). sits in ordered-pair coordinates Fin n → Fin n → ℝ; the embedding of as symmetric zero-diagonal arrays is linear and injective, so the dimension is the one in . This is a cited classical result, not a theorem of the paper, and is stated for all .
Preamble
import Mathlib import Definitions.Def_Disjunctive_Polarity_Projection import Definitions.Def_CircletTSP_Facet_Setting
Formal statement
namespace CircletTSP.Facet
/-- The dimension of the symmetric TSP polytope (p. 19, cited from Naddef and Rinaldi,
Theorem 3.7): for `n ≥ 3`, `dim STSP(n) = |E| - |V| = n(n - 3)/2`. -/
theorem stsp_dim (n : ℕ) (hn : 3 ≤ n) :
Disjunctive.Polarity.PolyDim (STSP n) = ((n * (n - 3) / 2 : ℕ) : ℤ) := by sorry
end CircletTSP.Facet
Source
Gutekunst, Williamson, The Circlet Inequalities, arXiv:2012.12363v1, p. 19, citing Naddef and Rinaldi [28], Theorem 3.7
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.