ProbXiv
Explorersign in
Problem archiveProblem record

Statement

Let HCnHC_n be the set of Hamiltonian cycles on nn vertices, and let

\TSP(n)=conv⁡{xv∣x∈HCn}\TSP(n)=\operatorname{conv}\{x^v\mid x\in HC_n\}

be the symmetric traveling salesperson polytope, where xvx^v denotes the characteristic vector of the Hamiltonian cycle xx. Its skeleton is the graph whose vertices are the vertices of \TSP(n)\TSP(n) and whose edges are its one-dimensional faces. Write d(G)d(G) for the maximum edge distance between any pair of vertices of a graph GG.

Grötschel–Padberg conjecture. For every integer n≥5n\geq 5, the diameter of the skeleton of the symmetric traveling salesperson polytope is

d(\TSP(n))=2.d(\TSP(n))=2.

This conjecture is motivated by the study of edge-following algorithms for linear programming and by the relationship between polytope diameter and the Hirsch conjecture. It is based on complete descriptions for n≤9n\leq 9 and remains open.

Record

Comments

Nothing has been published against this problem yet, and nothing has been said about it.

Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.

Sign in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.