All 0-1 polytopes are traveling salesman polytopes (Q1924487): Difference between revisions

Two permutation polytopes are studied: the assignment polytope \(B_n\), defined as the convex hull of the set of \(n\times n\) permutation matrices, and the asymmetric traveling salesman polytope (TSP) \(T_n\), defined as the convex hull of the set of those \(n\times n\) permutation matrices corresponding to \(n\)-cycles. It is proved that the face lattice of \(B_n\) is isomorphic to the lattice of all elementary subgraphs of \(K_{n,n}\), the complete bipartite graph with colour classes of size \(n\) (the elementary subgraphs are those having the property that each of its edges is in some matching), and that all faces of \(B_n\) have the property that any two vertices are contained in a cubical subface of dimension at most the integer part of \(n/2\). Concerning the TSP, the authors prove that any 0-1 polytope \(P \subset R^d\) with \(2^d-k\) vertices, \(k>1\), appears as a face of \(T_n\) for \(n\geq (4k+1)d\) and is the asymmetric TSP of some directed graph with \(n\) nodes (the asymmetric TSP \(T_D\) of the directed graph \(D\) is the convex hull of the set of permutation matrices associated to the tours in \(D)\). The maximum diameter of \(T_D\) over all directed graphs on \(n\) nodes is proved to be the integer part of \(n/3\).