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)

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

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)