The Cayley trick and triangulations of products of simplices

Abstract

We use the Cayley Trick to study polyhedral subdivisions of the product of two simplices. For arbitrary (fixed) $l$, we show that the numbers of regular and non-regular triangulations of ${\Delta }^l\times {\Delta }^k$ grow, respectively, as $k^{\Theta (k)}$ and $2^{\Omega (k^2)}$. For the special case of $l=2$, we relate triangulations to certain class of lozenge tilings. This allows us to compute the exact number of triangulations up to $k=15$, show that the number grows as $e^{\beta k^2/2+o(k^2)}$ where $\beta \simeq 0.32309594$ and prove that the set of all triangulations is connected under geometric bistellar flips. The latter has as a corollary that the toric Hilbert scheme of the determinantal ideal of $2\times 2$ minors of a $3\times k$ matrix is connected, for every $k$. We include ``Cayley Trick pictures'' of all the triangulations of ${\Delta }^2\times {\Delta }^2$ and ${\Delta }^2\times {\Delta }^3$, as well as one non-regular triangulation of ${\Delta }^2\times {\Delta }^5$ and one of ${\Delta }^3\times {\Delta }^3$.

This version has been accepted in "Proceedings of the Joint Summer Research Conference on Integer Points in Polyhedra" (Barvinok et al., eds.) Contemporary Mathematics, American Mathematical Society. Changes from v2: corrected a LaTeX problem with figures. Changes from v1: (1) some rephrasing, especially in the introduction. (2) the former proof of Theorem 5.4 was incorrect. The bound in the statement has been changed to match the new proof