On the maximum number of Latin transversals

Abstract

Let $T(n)$ denote the maximal number of transversals in an order-$n$ Latin square. Improving on the bounds obtained by McKay et al., Taranenko recently proved that $T(n)\le {\left((1+o(1))\frac{n}{e^2}\right)}^n$, and conjectured that this bound is tight. We prove via a probabilistic construction that indeed $T(n)={\left((1+o(1))\frac{n}{e^2}\right)}^n$. Until the present paper, no superexponential lower bound for $T(n)$ was known. We also give a simpler proof of the upper bound.