Let $n \ge 2$ be an integer and consider the
set $T_n$ of $n \times n$ permutation matrices $\pi$ for
which $\pi_{ij}=0$ for $j\ge i+2$.
¶ We study the convex hull $P_n$ of $T_n$, a polytope of dimension
$\binom{n}{2}$. 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_{i=0}^{n-2} \frac{1}{i+1}\BINOM{2i}{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 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.