All 0-1 polytopes are traveling salesman polytopes
type: Item
instance of: scholarly article
title: All 0-1 polytopes are traveling salesman polytopes
zbMATH Open document ID: 0859.52002
DOI: 10.1007/BF01844844
author: A. Sarangarajan
author: Billera, Louis J.
published in: Combinatorica
publication date: 1996-10-20T00:00:00Z
review text: 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\).
Mathematics Subject Classification ID: 52B12
Mathematics Subject Classification ID: 52B05
Mathematics Subject Classification ID: 90C27
zbMATH DE Number: 936869
zbMATH Keywords: permutation polytopes
zbMATH Keywords: assignment polytope
zbMATH Keywords: asymmetric traveling salesman polytope
zbMATH Keywords: 0--1 polytope
reviewed by: Juan-Enrique Martínez-Legaz
MaRDI profile type: Publication
cites work: Q4026491
cites work: Q4867143
cites work: Convex polyhedra of doubly stochastic matrices III. Affine and combinatorial properties of \(\Omega\)
cites work: Adjacency of the Traveling Salesman Tours and $0 - 1$ Vertices
cites work: Lectures on Polytopes
full work available at URL: https://doi.org/10.1007/bf01844844
OpenAlex ID: W1989428327
description: scientific article; zbMATH DE number 936869