Faces of Birkhoff Polytopes

DOI10.48550/ARXIV.1304.3948MaRDI QIDQ161295zbMATH OpenFDO

Authors Andreas Paffenholz, Andreas Paffenholz

Publication date 14 April 2013

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1304.3948, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p67

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

Birkhoff dimension Birkhoff polytope elementary graphs face lattice lattice polytope low dimensional classification permutation polytope

Mathematics Subject Classification ID

Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Lattices and convex bodies in (n) dimensions (aspects of discrete geometry) (52C07)

Abstract: The Birkhoff polytope B(n) is the convex hull of all (n x 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 L of faces of a Birkhoff polytope. The Birkhoff dimension bd(L) of L is the smallest n such that B(n) has a face with combinatorial type L. By a result of Billera and Sarangarajan, a combinatorial type L of a d-dimensional face appears in some B(k) for k less or equal to 2d, so bd(L) is at most d. We will characterize those types whose Birkhoff dimension is at least 2d-3, and we prove that any type whose Birkhoff dimension is at least d is either a product or a wedge over some lower dimensional face. Further, we computationally classify all d-dimensional combinatorial types for d between 2 and 8.

Review text

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\).

Recommendations

Cites work

Cited in

(19)

Describes a project that uses

Uses Software

This page was built for publication: Faces of Birkhoff Polytopes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q161295)