On the Volume of a Certain Polytope

Abstract

Let n ≥ 2 be an integer and consider the set T_n of n × n permu tation matrices π for wh ich π _ij = 0 for j ≥ i + 2.

We study the convex hull P_n of T_n, a polytope of dimension (ⁿ ₂). We provide evidence for several conjectures involving P_n, including Conjecture 1: 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 time s the product

of the first n – 1 Catalan numbers.

We also give a related result on the Ehrhart polynomial of P_n.

Editor's note: After this paper was circulated, Doron Zeilberger [1998] proved Conjecture 1, using the authors' reduction of the original problem to a conjectural comb inatorial identity, and sketched the proofs of two others. The problems and methodology presented here gain even further interest thereby.