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

volumeconvex hullpermutation matricespolytopeCatalan numberscombinatorial identityEhrhart polynomial

Mathematics Subject Classification ID

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

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

• scientific article; zbMATH DE number 273025 (Why is no real title available?)
• Decompositions of Rational Convex Polytopes
• 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

(58)

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

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)