123-avoiding doubly stochastic matrices (Q6565834)

This paper investigates the convex polytope \(\Omega_n(\overline{123})\) of doubly stochastic matrices that are spanned by the \(n\times n\) permutation matrices, that are \(123\)-avoiding or avoid an increasing pattern of length \(3\). A permutation matrix \(P = [\sigma(1) | \sigma(2) | \cdots | \sigma(n)]\) of a permutation \(\sigma : \{1,\ldots,n\}\rightarrow \{1,\ldots,n\}\) is \emph{\(123\)-avoiding}, or \emph{avoids} the pattern \(123\), if there are no \(i,j,k\in\{1,\ldots,n\}\) with \(i < j < k\) and \(\sigma(i) < \sigma(j) < \sigma(k)\). This is the same as \(P\) not having the \(3\times 3\) identity matrix \(I_3\) as a submatrix. First the authors determine the facets of the \(4\)-dimensional simplex \(\Omega_3(\overline{123})\). Next the convex polytope \(\Omega_n(\overline{123})\) is considered and certain of its facets are determined by using the notion of a blocking matrix. Small dimensional faces of \(\Omega_n(\overline{123})\) are also investigated in relation to the small dimensional faces of the convex polytope \(\Omega_n\) of all the \(n\times n\) stochastic matrices spanned by all \(n\times n\) permutation matrices. The frequencies of the positions of the \(1\)'s in \(n\times n\) \(123\)-avoiding permutation matrices are investigated and finally the paper makes some observation about the graph, or \(1\)-skeleton, of the polytope \(\Omega_n(\overline{123})\).