is_tsp_tour
def
A tour on a finite set V is a permutation σ of V that forms an n-cycle (it is a cycle and has full support).
Statement
def is_tsp_tour {V : Type*} [Fintype V] [DecidableEq V] (σ : Equiv.Perm V) : Prop
- Defined in
- arXiv:2611.09421 Section 1
- Verified
- 10 Nov 2026
- Axioms
- none listed
- Used by 1
- tsp_optOPT is the infimum length of a tour on V under edge weights ℓ.
Read back from the Lean
Given a finite type V with decidable equality and a permutation σ : Equiv.Perm V, is_tsp_tour σ defines the proposition that σ is a cycle (in the sense of Equiv.Perm.IsCycle) and the support of σ (the finite set of elements moved by σ) is the entire type Finset.univ. In other words, σ is a single cyclic permutation that visits every element of V without any fixed points.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- A tour on a finite set V is a cyclic permutation of full support. -/ def is_tsp_tour {V : Type*} [Fintype V] [DecidableEq V] (σ : Equiv.Perm V) : Prop := σ.IsCycle ∧ σ.support = Finset.univ