Let $Q_n$ denote the $n$ dimensional hypercube graph (i.e., graph formed from the vertices and edges of an n-dimensional hypercube). Denote the set of edges and vertices of $Q_n$ by $E_n$ and $V_n$ respectively.

We denote by ${H}_n$ the convex hull of the edge incidence vectors of the hamiltonian cycles of $Q_n$. This polytope is also known as the Hamiltonian cycle polytope or the symmetric traveling salesman polytope.

For any $S\subset V$ denote by $\delta(S)$ the set of edges with one end-vertex in $S$. Similarly, denote by $E(S)$ the set of edges with both end-vertices in $S$. Given $x\in \mathbb{R}^{|E_n|}$ and $F\subset E_n$ denote by $x(F)=\sum_{e\in F} x_e$.

Consider the associated subtour elimination polytope $P_n=\{x \in \mathbb{R}^{|E_n|} | 0\leq x\leq 1,~ x(\delta(i))=2 ~\mbox{$\forall i\in V_n$, } x(E(S))\leq |S|-1, \forall S\subset V\}$.

My questions are the following:

  1. Is it the case that $P_n = H_n$?
  2. If not, is there a simple set of inequalities that define $H_n$?

I have seen papers that characterize the Hamiltonian cycle polytope for complete graphs, but I haven't found anything for the hypercube graph. The following paper exploits the graph structure when it is bipartite (hence is useful for thinking about the hypercube graph), but it doesn't provide an answer to my questions: https://arxiv.org/pdf/1703.10821.pdf

  • 1
    $\begingroup$ I don't see how this will help, but maybe worth mentioning: Every perfect matching in $Q_n$ extends to a Hamiltonian cycle. This is Kreweras' conjecture, now established by J. Fink. $\endgroup$ – Joseph O'Rourke May 3 '18 at 12:19

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.