On the volume of a certain polytope. (English) Zbl 0960.05004

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

Exp. Math. 9, No. 1, 91-99 (2000).

Summary: Let \(n\geq 2\) be an integer and consider the set \(T_n\) of \(n\times n\) permutation matrices \(\pi\) for which \(\pi_{ij}= 0\) for \(j\geq i+2\). We study the convex hull \(P_n\) of \(T_n\), a polytope of dimension \(\left(\begin{smallmatrix} n\\ 2\end{smallmatrix}\right)\). 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\) times the product \[ \prod^{n-2}_{i= 0}{1\over i+1}{2i\choose i} \] 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 [Proof of a conjecture of Chan, Robbins, and Yuen, ETNA, Electron. Trans. Numer. Anal. 9, 147-148, electronic only (1999; Zbl 0941.05006)] proved Conjecture 1, using the authors’ reduction of the original problem to a conjectural combinatorial identity, and sketched the proofs of two others. The problems and methodology presented here gain even further interest thereby.

MSC:

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

Keywords:

permutation matrices; convex hull; polytope; volume; Catalan numbers; Ehrhart polynomial; combinatorial identity

Citations:

Zbl 0941.05006

References:

[1]	Billera L. J., Formal power series and algebraic combinatorics (New Brunswick, NJ, 1994) pp 1– (1996)
[2]	DOI: 10.1080/10586458.1999.10504406 · Zbl 0951.05015 · doi:10.1080/10586458.1999.10504406
[3]	DOI: 10.1007/978-1-4612-0801-3_3 · doi:10.1007/978-1-4612-0801-3_3
[4]	Ehrhart E., Polynômes arithmétiques et méthode des polyedres en combinatoire (1977) · Zbl 0337.10019
[5]	Hibi T., Algebraic combinatorics on convex polytopes (1992) · Zbl 0772.52008
[6]	Postnikov, A. and Stanley, R. P. 1998. [Postnikov and Stanley 1998], Private communication
[7]	DOI: 10.1016/S0167-5060(08)70717-9 · Zbl 0812.52012 · doi:10.1016/S0167-5060(08)70717-9
[8]	Zeilberger D., ”Proof of a conjecture of Chan, Robbins and Yuen” (1998) · Zbl 0941.05006