# Hamilton Path Polytope

How can someone prove that the $\{dim(H)=\frac{n(n-1)}{2} uncorrect\ see\ update\}$ where $H$ is the Hamilton path polytope of a complete graph $K_n$, that consists of vertices $x\in\{0,1\}^{\mid E\mid}$

Update: I really did a silly mistake it's $\frac{n(n-1)}{2}-1$

Update:

Definition: The polytope of all Hamilton paths in a graph G=(V,E) is the convex hull of $\{x_1,\ldots,x_n\}$ characteristic vectors of those paths.

• I don't really know what the Hamilton path polytope is. But the dimension appears to be $|E|$, since that's the dimension of the space the vertices live in, and of course the edge set of the complete graph $K_n$ has cardinality $\binom{n}{2} = \frac{n(n-1)}{2}$. Does that answer the question? Commented Nov 30, 2014 at 3:56
• Sorry Kundor please check again. It's about affine independence but I can't see the connection...
– Lpax
Commented Nov 30, 2014 at 11:36
• @Lpax: perhaps you can define the Hamilton path polytope? I've also not heard of it before. Commented Nov 30, 2014 at 12:29

Here's my understanding of the construction. We take the set of edges $E$ of some graph $G$, and index them $E = \{e_1, \dotsc, e_m\}$ in some arbitrary order, where $m = |E|$. Then, to each Hamiltonian path in $G$ (i.e. a path visiting every vertex exactly once), we associate a point in $\mathbb{R}^m$ whose $i$th coordinate is $1$ if $e_i$ is in the path, and $0$ otherwise (the "characteristic vector" of the path). The convex hull $P$ of all these points is the "Hamilton path polytope" of $G$.

When $G = K_n$, then $m = \binom{n}{2}$. The affine dimension of $P$ is therefore at most $\binom{n}{2}$. Since every Hamiltonian path has $n - 1$ edges, every characteristic vector contains exactly $n-1$ coordinates which are $1$. Thus the whole polytope $P$ lies in the hyperplane where the sum of all the coordinates is $n-1$; so the affine dimension of $P$ is at most $\binom{n}{2} - 1$.

On the other hand, pick an ordering of the edges so that the first $n$ edges $e_1, \dotsc, e_n$ form a cycle $C$ in $G$. Leaving out any one of these yields a Hamiltonian path, and the characteristic vectors of the $n$ Hamiltonian paths thus obtained are linearly independent. To see this, just check that the determinant of the $n \times n$ matrix $$(1 - \delta_{ij})_{i,j} = \begin{bmatrix} 0 & 1 & 1 & \cdots & 1 \\ 1 & 0 & 1 & \cdots & 1 \\ 1 & 1 & 0 & & \vdots \\ \vdots & \vdots & & \ddots & 1 \\ 1 & 1 & \cdots & 1 & 0 \end{bmatrix}$$ is nonzero. In fact, it's $(-1)^{n-1}(n-1)$.

Now consider each edge from $e_{n+1}$ up to $e_m$. Let $e_j$ be such an edge. Because $G$ is a complete graph, we can find a Hamiltonian path using $e_j$ and otherwise only edges from $\{ e_i \mid i < j \}$. In fact, since $e_j$ is a chord in the cycle $C$, we can find such a path using just edges from $C$, as suggested by this picture:

It follows that for each $j$ there is a characteristic vector whose nonzero entries are either among the first $n$, or in the never-before-used $j$th coordinate; it is thus linearly independent from all the previously added vectors.

In this way, we build a set of $m = \binom{n}{2}$ linearly independent vectors among the points in $P$. If they are linearly independent, then they are certainly affinely independent. So there is a set of at least $\binom{n}{2}$ affinely independent vectors among our points; therefore the affine dimension is at least $\binom{n}{2} - 1$.

Remembering the upper bound from the beginning, we conclude that the affine dimension is exactly $\binom{n}{2} - 1$.

• Thank you a lot! That is almost what I had in mind but I could not formulate with words. One question though. For the lower bound you state that there are $\binom{n}{2}$ linearly independent vectors. We should not add the zero vector because it is not a correct hamiltonian cycle. Am I correct?
– Lpax
Commented Dec 25, 2014 at 11:09
• @Lpax: The zero vector isn't the characteristic vector of a hamiltonian cycle. It's also not in the affine hull of the polytope. I'm not sure why you mention it. Commented Dec 30, 2014 at 16:41
• For an example, if the graph is $K_4$, the 6 linearly independent vectors we find are $(0,1,1,1,0,0), (1,0,1,1,0,0),(1,1,0,1,0,0),(1,1,1,0,0,0),(1,0,1,0,1,0),(1,0,1,0,0,1)$. The linear span of these guys has dimension 6. If the linear span of some set has dimension $m$, then the affine dimension is either $m$ or $m-1$. Commented Dec 30, 2014 at 16:57