3
$\begingroup$

Given the complete graph $K_n=(V,E)$, the Traveling Salesman Polytope is a convex polytope in $\Bbb R^E$ obtained as the convex hull of the indicator vectors of (edge-sets of) Hamiltonian cycles in $K_n$.

  • for $n=3$ it is a single point,
  • for $n=4$ it is a regular triangle.

For $n = 5$ I found that the polytope has many more geometric symmetries than can be explained by the $5!$ automorphisms of $K_5$. In fact, I found $2\cdot 6!=1440$ symmetries.

What about higher dimensions?

Question: Have the symmetry groups and these "additional symmetries" of the Traveling Salesman Polytope been studied before? Where can I read about this?

Improve this question
$\endgroup$
8
  • 1
    $\begingroup$ Can you post some code that computes this? In particular, what is the structure of the group of order $1440$? Are you able to do this computation for $n=6$? $\endgroup$
    – verret
    Commented Jan 19, 2021 at 0:39
  • $\begingroup$ @verret My computations are still a bit sketchy. I constructed a subgraph of the edge-graph for which every symmetry extends to a symmetry of the polytope. For $n=5$ this is the crown graph on 12 vertices (so its symmetry group should be $S_6\times S_2$). I just now finished the computation for $n\in\{7,8\}$ and I am a bit disappointed to find that their symmetry groups are just of size $n!$. It seems $n=5$ is exceptional. Anyway, if there is any literature that deals with the symmetries of the TSP polytopes I would be interested. $\endgroup$
    – M. Winter
    Commented Jan 19, 2021 at 0:51
  • $\begingroup$ (There was a mistake in my deleted comment, it's not the double cover of $S_6$, but $S_6\times S_2$.) $\endgroup$
    – verret
    Commented Jan 19, 2021 at 0:52
  • $\begingroup$ I think an upper bound is given by the $2$-closure (in the sense of Wielandt) of $S_n$ acting on the cosets of $D_n$. It might be that a carefully chosen orbital graph already shows that we get $S_n$ in general. $\endgroup$
    – verret
    Commented Jan 19, 2021 at 1:00
  • $\begingroup$ Maybe the exceptional behavior for $n=5$ is due to two anomalies, one combinatorial and one group-theoretic. In the complete graph $K_5$, the complement of a $5$-cycle is a $5$-cycle, which should explain the central $Z_2$. The stabilizer of a point in the action of $S_5$ on $5$-cycles in $K_5$ is $D_{10}$, and the action of $S_5$ on the cosets of $D_{10}$ should extend to an action of $S_6$ on the cosets of a subgroup isomorphic with $A_5$, this last subgroup being transitive on six points. I guess that this action gives the $S_6$, although I do not see why. $\endgroup$
    – John Shareshian
    Commented Jan 19, 2021 at 20:38

0

Reset to default

You must log in to answer this question.