Faces of Birkhoff Polytopes (Q161295)

Summary: The Birkhoff polytope \(B_n\) is the convex hull of all \((n\times n)\) permutation matrices, i.e., matrices where precisely one entry in each row and column is one, and zeros at all other places. This is a widely studied polytope with various applications throughout mathematics. In this paper we study combinatorial types \(\mathcal L\) of faces of a Birkhoff polytope. The Birkhoff dimension \(\mathrm{bd}(\mathcal L)\) of \(\mathcal L\) is the smallest \(n\) such that \(B_n\) has a face with combinatorial type \(\mathcal L\). By a result of Billera and Sarangarajan, a combinatorial type \(\mathcal L\) of a \(d\)-dimensional face appears in some \(\mathcal B_k\) for \(k\leqslant 2d\), so \(\mathrm{bd}(\mathcal L)\leqslant 2d\). We characterize those types with \(\mathrm{bd}(\mathcal L)\geqslant 2d-3\), and we prove that any type with \(\mathrm{bd}(\mathcal L)\geqslant d\) is either a product or a wedge over some lower dimensional face. Further, we computationally classify all \(d\)-dimensional combinatorial types for \(2\leqslant d\leqslant 8\).