The Cayley trick and triangulations of products of simplices

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 ${\mathrm{\Delta }}^l\times {\mathrm{\Delta }}^k$ grow, respectively, as $k^{\mathrm{\Theta }(k)}$ and $2^{\mathrm{\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\mathrm{/}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 ${\mathrm{\Delta }}^2\times {\mathrm{\Delta }}^2$ and ${\mathrm{\Delta }}^2\times {\mathrm{\Delta }}^3$, as well as one non-regular triangulation of ${\mathrm{\Delta }}^2\times {\mathrm{\Delta }}^5$ and one of ${\mathrm{\Delta }}^3\times {\mathrm{\Delta }}^3$.