# Why is the Symmetric Traveling Salesman Polytope not a full dimensional polytope?

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)
• I am not very familiar with this polytope, so this might be bogus. However, we know that every Hamilton cycle has exactly $|V|$ edges, and so for every point $x$ in the polytope, we must have $\sum_i x_i = |V|$. Would this explain why the polytope is not full-dimensional? Commented Aug 1, 2016 at 14:57
• I am not sure. I think it has to do with the number of $|V|$ as well. I just added the definition of affinely independent. But you are saying that there does not always exist a combination of incidence vectors (solutions of the STSP) that satisfy the affinely independent definition? Why is that true?
– M.C.
Commented Aug 1, 2016 at 15:31
• An equivalent definition to the polytope being full-dimensional is that it should have $n+1$ points $v_0, ... , v_n$ such that the $n$ vectors $v_i - v_0$, $1 \le i \le n$, span $\mathbb {R}^n$. However, since $v_j \cdot \mathbf{1} = |V|$ for all $j$, these vectors are all orthogonal to the all-one vector $\mathbf {1}$. Commented Aug 1, 2016 at 16:18

There are many additional affine constraints that a characteristic vector $$\chi$$ of a Hamiltonian cycles must satisfy. Besides the one mentioned by Mariano (all these vectors contain the same number of edges), here are further ones:
For every vertex $$v\in V(G)$$, consider the set $$E_v$$ of edges incident to $$v$$. Exactly two of these are containd in a Hamiltonian cycle. Hence, any characteristic vector $$\chi$$ of a Hamiltonian cycle satisfies $$\sum_{e\in E_v} \chi_e = 2.$$ for all $$v\in V(G)$$.
This is a set of $$|V(G)|$$ linear constraints, but not all of them are affinely independent.