On the Volume of a Certain Polytope

DOI10.1080/10586458.2000.10504639MaRDI QIDQ4506293zbMATH OpenOpenAlexFDO

Authors David P. Robbins, David S. Yuen, Clara S. Chan

Publication date 20 May 2001

Published in Experimental Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/9810154, https://eudml.org/doc/226644

zbMATH Keywords

Catalan numberscombinatorial identityconvex hullEhrhart polynomialpermutation matricespolytopevolume

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Combinatorial identities, bijective combinatorics (05A19) Length, area, volume and convex sets (aspects of convex geometry) (52A38) Inequalities and extremum problems involving convexity in convex geometry (52A40) Lattice polytopes in convex geometry (including relations with commutative algebra and algebraic geometry) (52B20)

Abstract: Let n >= 2 be an integer and consider the set T_n of n by n permutation matrices pi for which pi_{ij}=0 for j>=i+2. In this paper we study the convex hull of T_n, which we denote by P_n. P_n is a polytope of dimension binom{n}{2}. Our main purpose is to provide evidence for the following conjecture concerning its volume. Let v_n denote the minimum volume of a simplex with vertices in the affine lattice spanned by T_n. Then the volume of P_n is v_n times the product for i varying from 0 to n-2 of frac{1}{i+1} binom{2i}{i}. That is, P_n is the product of v_n and the first n-1 Catalan numbers. We also give a related result on the Ehrhart polynomial of P_n.

Recommendations

• Permutohedra, Associahedra, and Beyond
• On volumes of permutation polytopes
• The equivariant volumes of the permutahedron
• Ehrhart polynomials, simplicial polytopes, magic squares and a conjecture of Stanley
• The alternating sign matrix polytope

Cites work

• Decompositions of Rational Convex Polytopes
• scientific article; zbMATH DE number 273025 (Why is no real title available?)
• On the Volume of the Polytope of Doubly Stochastic Matrices
• Polynômes arithmétiques et méthode des polyedres en combinatoire
• Proof of a conjecture of Chan, Robbins, and Yuen

Cited in

(61)

• Kostant partitions functions and flow polytopes
• The volume of relaxed Boolean-quadric and cut polytopes
• The Ehrhart polynomial of the Birkhoff polytope
• A polytope related to empirical distributions, plane trees, parking functions, and the associahedron
• Faces of Birkhoff Polytopes
• Volume polynomial for polyhedra of hexaedral type
• Flow polytopes of partitions
• On the mean radius of permutation polytopes
• Surface volumes of rounding polytopes
• On the even permutation polytope
• Commutative algebra of statistical ranking
• Acyclic systems of permutations and fine mixed subdivisions of simplices
• Volumes of flow polytopes related to caracol graphs
• Kostant's partition function and magic multiplex juggling sequences
• Volumes of generalized Chan-Robbins-Yuen polytopes
• Volumes and Ehrhart polynomials of flow polytopes
• Leading coefficients of Morris type constant term identities
• How many times can the volume of a convex polyhedron be increased by isometric deformations?
• On flow polytopes, order polytopes, and certain faces of the alternating sign matrix polytope
• On a conjecture by Dehornoy
• Cone-volume measures of polytopes
• Volumes of degenerating polyhedra -- on a conjecture of J. W. Milnor
• Bayesian analysis for reversible Markov chains
• The volume of the caracol polytope
• Ehrhart positivity of Tesler polytopes and Berline-Vergne's valuation
• On volumes of permutation polytopes
• A conjectural non-commutative generalization of a volume formula of McMullen-Schneider
• A practical volume algorithm
• scientific article; zbMATH DE number 5990521 (Why is no real title available?)
• On product formulas for volumes of flow polytopes
• scientific article; zbMATH DE number 5697553 (Why is no real title available?)
• The combinatorics of interval vector polytopes
• scientific article; zbMATH DE number 151804 (Why is no real title available?)
• scientific article; zbMATH DE number 1734677 (Why is no real title available?)
• On the Sums ∑ k = -∞ ∞ (4k + 1) -n
• Volumes of convex lattice polytopes and a question of V. I. Arnold
• Constrained triangulations, volumes of polytopes, and unit equations
• The polytope of Tesler matrices
• A Short Proof for the Volume of Square Pyramids
• On a Formula for the Volume of Polytopes
• Flow polytopes with Catalan volumes
• A combinatorial model for computing volumes of flow polytopes
• Volumes of Polytopes in Spaces of Constant Curvature
• Product formulas for volumes of flow polytopes
• Pattern-avoiding polytopes
• The equivariant volumes of the permutahedron
• Column-convex matrices, G-cyclic orders, and flow polytopes
• On the volume product of polygons
• Deformation cones of Tesler polytopes
• The fraction of an \(S_n\)-orbit on a hyperplane
• Equidistant circular split networks
• Capacity bounds on integral flows and the Kostant partition function
• On faces of partial alternating sign matrix polytopes
• A generating function for all semi-magic squares and the volume of the Birkhoff polytope
• On the f-vectors of flow polytopes for the complete graph
• Extensions of partial cyclic orders and consecutive coordinate polytopes
• Refinements and symmetries of the Morris identity for volumes of flow polytopes
• On permutation polytopes
• h-polynomials via reduced forms
• On some quadratic algebras. I \(\frac{1}{2}\): Combinatorics of Dunkl and Gaudin elements, Schubert, Grothendieck, Fuss-Catalan, universal Tutte and reduced polynomials
• A solution to one of Knuth's permutation problems

This page was built for publication: On the Volume of a Certain Polytope

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