Faces of Birkhoff Polytopes

DOI10.48550/ARXIV.1304.3948MaRDI QIDQ161295zbMATHFDO

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

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 dimensionBirkhoff polytopeelementary graphsface latticelattice polytopelow dimensional classificationpermutation 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.

Recommendations

• Faces of faces of the acyclic Birkhoff polytope
• Faces of faces of the tridiagonal Birkhoff polytope
• The number of faces of the tridiagonal Birkhoff polytope
• Face counting on an acyclic Birkhoff polytope
• Faces of root polytopes
• On the faces of simple polytopes
• scientific article; zbMATH DE number 1182908
• scientific article; zbMATH DE number 4100062
• On the vertices of the \(d\)-dimensional Birkhoff polytope
• Polytopes with parathetic faces

Cites work

• scientific article; zbMATH DE number 6016068 (Why is no real title available?)
• scientific article; zbMATH DE number 1944136 (Why is no real title available?)
• scientific article; zbMATH DE number 1857822 (Why is no real title available?)
• scientific article; zbMATH DE number 795108 (Why is no real title available?)
• scientific article; zbMATH DE number 848091 (Why is no real title available?)
• A Simplified Form for Nearly Reducible and Nearly Decomposable Matrices
• A generating function for all semi-magic squares and the volume of the Birkhoff polytope
• Advances in Mathematical Optimization
• Convex polyhedra of doubly stochastic matrices III. Affine and combinatorial properties of \(\Omega\)
• Convex polyhedra of doubly stochastic matrices. I: Applications of the permanent function
• Convex polyhedra of doubly stochastic matrices. II: Graph of Omega sub(n)
• Convex polyhedra of doubly stochastic matrices. IV
• Cutsets in bipartite graphs^*
• Ear decompositions of matching covered graphs
• Ear-decompositions of matching-covered graphs
• Ehrhart polynomials, simplicial polytopes, magic squares and a conjecture of Stanley
• Faces of Birkhoff Polytopes
• Four questions on Birkhoff polytopes
• Geometry, complexity, and combinatorics of permutation polytopes
• Graph isomorphism and theorems of Birkhoff type
• Graphs with independent perfect matchings
• Lectures on Polytopes
• Matching theory
• On a conjecture of Lovász concerning bricks. I: The characteristic of a matching covered graph
• On permutation polytopes
• On the Volume of a Certain Polytope
• On the Volume of the Polytope of Doubly Stochastic Matrices
• On the even permutation polytope
• Optimal ear decompositions of matching covered graphs and bases for the matching lattice
• Permutation polytopes and indecomposable elements in permutation groups
• Polytopes associated to dihedral groups
• Proof of a conjecture of Chan, Robbins, and Yuen
• Some applications of doubly stochastic matrices
• Some facets of the polytope of even permutation matrices.
• The Distribution of Values in the Quadratic Assignment Problem
• The Ehrhart polynomial of the Birkhoff polytope
• The asymptotic volume of the Birkhoff polytope
• The polytope of even doubly stochastic matrices
• polymake: a framework for analyzing convex polytopes

Cited in

(14)

• A property of the Birkhoff polytope
• Faces of root polytopes in all dimensions
• Unconditional reflexive polytopes
• Faces of faces of the tridiagonal Birkhoff polytope
• The number of faces of the tridiagonal Birkhoff polytope
• Enumerating extreme points of the polytopes of stochastic tensors: an optimization approach
• \texttt{polyDB}: a database for polytopes and related objects
• scientific article; zbMATH DE number 848091 (Why is no real title available?)
• An intermediate value theorem for face polytopes
• The face structure and geometry of marked order polyhedra
• Faces of Birkhoff Polytopes
• Polytopes.Combinatorial.FacesBirkhoffPolytope
• Tropical positivity and determinantal varieties
• On Faces of Quasi-arithmetic Coxeter Polytopes

Describes a project that uses

Uses Software

• polymake
• birkhoff faces
• GitHub

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)