Faces of Birkhoff Polytopes

DOI10.48550/ARXIV.1304.3948zbMATH Open1311.52015arXiv1304.3948MaRDI QIDQ161295FDOQ161295

Andreas Paffenholz, Andreas Paffenholz

Publication date: 14 April 2013

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

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.

Full work available at URL: https://arxiv.org/abs/1304.3948

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)

Cites Work

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

Cited In (12)

• The number of faces of the tridiagonal Birkhoff polytope
• On Faces of Quasi-arithmetic Coxeter Polytopes
• An intermediate value theorem for face polytopes
• The face structure and geometry of marked order polyhedra
• Faces of root polytopes in all dimensions
• polyDB: A Database for Polytopes and Related Objects
• Unconditional reflexive polytopes
• Tropical positivity and determinantal varieties
• Enumeration of 2-level polytopes
• Faces of Birkhoff Polytopes
• Polytopes.Combinatorial.FacesBirkhoffPolytope
• Enumerating extreme points of the polytopes of stochastic tensors: an optimization approach

Uses Software

• polymake
• birkhoff faces
• GitHub

Recommendations

• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• On the vertices of the \(d\)-dimensional Birkhoff polytope 👍 👎
• Faces of Root Polytopes 👍 👎
• On the faces of simple polytopes 👍 👎
• Faces of faces of the acyclic Birkhoff polytope 👍 👎
• The number of faces of the tridiagonal Birkhoff polytope 👍 👎
• Faces of faces of the tridiagonal Birkhoff polytope 👍 👎
• Face counting on an acyclic Birkhoff polytope 👍 👎

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)