More Vertices of the Tristochastic Polytope

Abstract

The $n\times n$ doubly stochastic matrices constitute a polytope in ${\mathbb{R}}^{n^2}$, and by Birkhoff's theorem, its vertex set coincides with the set of order-$n$ permutation matrices.\\ A tristochastic array is an $n\times n\times n$ array of nonnegative reals, where each row, column, and shaft sums to one. These arrays constitute a polytope $\hat{I}{”}_n$ in ${\mathbb{R}}^{n^3}$. In analogy, it is easy to see that each of the $L_n$ order-$n$ Latin squares is a vertex of $\hat{I}{”}_n$, but in contrast to Birkhoff's theorem, Latin squares form a vanishingly small subset of $\hat{I}{”}_n$'s vertex set. We show here that $\hat{I}{”}_n$ has at least $L_n^{2-o(1)}$ vertices.