The symmetric travelling salesman polytope (STSP) is defined as the convex hull of incidence vectors of Hamiltonian cycles.
Given a graph $G=(V,E)$, an incidence vector is a vector $v$ with length $n$ = $|E|$ and entries $0$ or $1$. $v_i=1$ means that the edge is considered in the tour represented by this incidence vector.
The dimension $dim(P)$ of a polyhedron $P ⊆ R^n$ is one less than the maximum number of affinely independent vectors in P. If $dim(P)$ = $n$, then we call $P$ full dimensional.
Definition: Let $v_0, v_1.. v_k$ be points in $\mathbb{R}^d$. These points are called affinely independent if there do not exist real numbers $\alpha_0, \alpha_1...\alpha_k$ that are not all zero such that $\sum_{i=0}^k \alpha_i v_i = 0$ and $\sum_{i=0}^k \alpha_i = 0$.
This is the background definitions of the problem, that might be needed.
My Question is how do we know that we do not have $n$ vectors in STSP that are affinely independent. I can not easily think how this is supposed to be obvious.
Here is two scientific papers that mention the fact that STSP is not full-dimensional:
- The paper "Worst Case Comparison Of Valid Inequalities For The TSP" by Michel X. Goemans (1995), and here is the link. (end of 2nd page)
- "The symmetric traveling salesman polytope and its graphical relaxation: Composition of valid inequalities" by Naddef & Rinaldi (1991) and here is a preview link. (middle of 2nd page)
All hamiltonian paths have the same number of edges, so the potyptope is contained in a hyperplane.