On the Volume of a Certain Polytope

DOI10.1080/10586458.2000.10504639zbMATH Open0960.05004arXivmath/9810154OpenAlexW1992133714MaRDI QIDQ4506293FDOQ4506293

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

Publication date: 20 May 2001

Published in: Experimental Mathematics (Search for Journal in Brave)

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.

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

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

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)

Cites Work

• Proof of a conjecture of Chan, Robbins, and Yuen
• Decompositions of Rational Convex Polytopes
• On the Volume of the Polytope of Doubly Stochastic Matrices
• Title not available (Why is that?)
• Polynômes arithmétiques et méthode des polyedres en combinatoire

Cited In (58)

• Column-convex matrices, \(G\)-cyclic orders, and flow polytopes
• The fraction of an \(S_n\)-orbit on a hyperplane
• Deformation cones of Tesler polytopes
• Equidistant circular split networks
• Volumes of generalized Chan-Robbins-Yuen polytopes
• Refinements and symmetries of the Morris identity for volumes of flow polytopes
• Volumes and Ehrhart polynomials of flow polytopes
• Pattern-avoiding polytopes
• The combinatorics of interval vector polytopes
• Surface volumes of rounding polytopes
• A generating function for all semi-magic squares and the volume of the Birkhoff polytope
• On permutation polytopes
• Volumes of degenerating polyhedra -- on a conjecture of J. W. Milnor
• A Short Proof for the Volume of Square Pyramids
• Leading coefficients of Morris type constant term identities
• Title not available (Why is that?)
• Volume polynomial for polyhedra of hexaedral type
• On volumes of permutation polytopes
• A conjectural non-commutative generalization of a volume formula of McMullen-Schneider
• The Ehrhart polynomial of the Birkhoff polytope
• On the even permutation polytope
• Volumes of flow polytopes related to caracol graphs
• A practical volume algorithm
• Commutative algebra of statistical ranking
• The volume of the caracol polytope
• Constrained triangulations, volumes of polytopes, and unit equations
• Title not available (Why is that?)
• 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
• 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
• Cone-volume measures of polytopes
• Volumes of Polytopes in Spaces of Constant Curvature
• Flow polytopes of partitions
• Title not available (Why is that?)
• On the volume product of polygons
• How many times can the volume of a convex polyhedron be increased by isometric deformations?
• On the Sums ∑ k = -∞ ∞ (4k + 1) -n
• Ehrhart positivity of Tesler polytopes and Berline-Vergne's valuation
• The volume of relaxed Boolean-quadric and cut polytopes
• The polytope of Tesler matrices
• Title not available (Why is that?)
• A combinatorial model for computing volumes of flow polytopes
• Product formulas for volumes of flow polytopes
• Flow polytopes with Catalan volumes
• Faces of Birkhoff Polytopes
• On the mean radius of permutation polytopes
• On a conjecture by Dehornoy
• Kostant partitions functions and flow polytopes
• Acyclic systems of permutations and fine mixed subdivisions of simplices
• On product formulas for volumes of flow polytopes

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)