123-avoiding doubly stochastic matrices
Permutations, words, matrices (05A05) Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20) Vector spaces, linear dependence, rank, lineability (15A03) Stochastic matrices (15B51) Convex sets in (n) dimensions (including convex hypersurfaces) (52A20) Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05)
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})\).
- Minimum permanents on a face of the polytope of doubly stochastic matrices
- Faces of the polytope of doubly substochastic matrices
- The polytope of even doubly stochastic matrices
- MINIMUM PERMANENTS OF DOUBLY STOCHASTIC MATRICES WITH k DIAGONAL p×p BLOCK SUBMATRICES
- Diagonal sums of doubly stochastic matrices
- Blockers of pattern avoiding permutation matrices
- Combinatorial matrix classes
- Combinatorics of permutations
- Convex polyhedra of doubly stochastic matrices. I: Applications of the permanent function
- Hamiltonicity and combinatorial polyhedra
- Hamiltonicity in (0-1)-polyhedra
- scientific article; zbMATH DE number 3159526 (Why is no real title available?)
- scientific article; zbMATH DE number 7731167 (Why is no real title available?)
- Pattern-avoiding polytopes
- The polytope of even doubly stochastic matrices
This page was built for publication: 123-avoiding doubly stochastic matrices
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6565834)
