Faces of Birkhoff Polytopes
type: Item
instance of: scholarly article
publication date: 2013-04-14T00:00:00Z
publication date: 2015-03-19T00:00:00Z
arXiv ID: 1304.3948
arXiv classification: math.CO
Mathematics Subject Classification ID: 52B12
Mathematics Subject Classification ID: 52B05
Mathematics Subject Classification ID: 52C07
author: Andreas Paffenholz
MaRDI profile type: Publication
title: Faces of Birkhoff polytopes
zbMATH Open document ID: 1311.52015
published in: The Electronic Journal of Combinatorics
full work available at URL: https://arxiv.org/abs/1304.3948
full work available at URL: v22i1p67
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\).
zbMATH DE Number: 6416845
zbMATH Keywords: Birkhoff polytope
zbMATH Keywords: Birkhoff dimension
zbMATH Keywords: lattice polytope
zbMATH Keywords: elementary graphs
zbMATH Keywords: permutation polytope
zbMATH Keywords: face lattice
zbMATH Keywords: low dimensional classification
describes a project that uses: polymake
describes a project that uses: birkhoff faces
describes a project that uses: GitHub
cites work: Ehrhart polynomials, simplicial polytopes, magic squares and a conjecture of Stanley
cites work: The Distribution of Values in the Quadratic Assignment Problem
cites work: Polytopes associated to dihedral groups
cites work: On permutation polytopes
cites work: The Ehrhart polynomial of the Birkhoff polytope
cites work: Q4867143
cites work: Q4788785
cites work: Some applications of doubly stochastic matrices
cites work: Convex polyhedra of doubly stochastic matrices. IV
cites work: Convex polyhedra of doubly stochastic matrices. I: Applications of the permanent function
cites work: Convex polyhedra of doubly stochastic matrices. II: Graph of Omega sub(n)
cites work: Convex polyhedra of doubly stochastic matrices III. Affine and combinatorial properties of \(\Omega\)
cites work: The polytope of even doubly stochastic matrices
cites work: Cutsets in bipartite graphs*
cites work: The asymptotic volume of the Birkhoff polytope
cites work: A generating function for all semi-magic squares and the volume of the Birkhoff polytope
cites work: Ear decompositions of matching covered graphs
cites work: On the Volume of the Polytope of Doubly Stochastic Matrices
cites work: On the Volume of a Certain Polytope
cites work: Optimal ear decompositions of matching covered graphs and bases for the matching lattice
cites work: On a conjecture of Lovász concerning bricks. I: The characteristic of a matching covered graph
cites work: Q4407444
cites work: Graphs with independent perfect matchings
cites work: On the even permutation polytope
cites work: Q4845257
cites work: Advances in Mathematical Optimization
cites work: polymake: a framework for analyzing convex polytopes
cites work: Permutation polytopes and indecomposable elements in permutation groups
cites work: A Simplified Form for Nearly Reducible and Nearly Decomposable Matrices
cites work: Some facets of the polytope of even permutation matrices.
cites work: Ear-decompositions of matching-covered graphs
cites work: Matching theory
cites work: Geometry, complexity, and combinatorics of permutation polytopes
cites work: Four questions on Birkhoff polytopes
cites work: Q3225387
cites work: Graph isomorphism and theorems of Birkhoff type
cites work: Proof of a conjecture of Chan, Robbins, and Yuen
cites work: Lectures on Polytopes
DOI: 10.48550/ARXIV.1304.3948
Recommended article: Faces of faces of the acyclic Birkhoff polytope
Recommended article: Faces of faces of the tridiagonal Birkhoff polytope
Recommended article: The number of faces of the tridiagonal Birkhoff polytope
Recommended article: Face counting on an acyclic Birkhoff polytope
Recommended article: Faces of Root Polytopes
Recommended article: On the faces of simple polytopes
Recommended article: Q4401005
Recommended article: Q3825654
Recommended article: On the vertices of the \(d\)-dimensional Birkhoff polytope
Recommended article: Q3446201
description: scientific article; zbMATH DE number 6416845

Faces of Birkhoff Polytopes (cites work)
cites work: Faces of Birkhoff Polytopes