Some facets of the polytope of even permutation matrices. (Q1430383): Difference between revisions

The Birkhoff polytope is the convex hull of the collection of all \(n\times n\) permutation matrices: it comprises precisely those real \(n\times n\) matrices that are doubly stochastic (i.e., the entries are non-negative and rows and columns sum up to 1). In this paper, the authors study the polytope of convex combinations of the collection of even \(n\times n\) permutation matrices. In particular, they describe a class of \(n!(n-1)!/2\) distinct facets of this polytope and hereby prove a conjecture by \textit{R. A. Brualdi} and \textit{B. Liu} [J. Comb. Theory, Ser. A 57, No. 2, 243--253 (1991; Zbl 0754.15017)] that the number of facets of this polytope is not bounded by a polynomial in \(n\).