Portal de Periódicos da CAPES

On the Volume of a Certain Polytope

2000; Taylor & Francis; Volume: 9; Issue: 1 Linguagem: Inglês

10.1080/10586458.2000.10504639

1944-950X

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

Coding theory and cryptography

Abstract Let n ≥ 2 be an integer and consider the set Tn of n × n permu tation matrices π for wh ich π ij = 0 for j ≥ i + 2. We study the convex hull Pn of Tn, a polytope of dimension (n 2). We provide evidence for several conjectures involving Pn, including Conjecture 1: Let Vn denote the minimum volume of a simplex with vertices in the affine lattice spanned by Tn. Then the volume of Pn is Vn time s the product of the first n – 1 Catalan numbers. We also give a related result on the Ehrhart polynomial of Pn. 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.