On the maximum number of Latin transversals

Original · EN

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) ≤ ((1+o(1))n/e²)ⁿ, and conjectured that this bound is tight. We prove via a probabilistic construction that indeed T(n) = ((1+o(1))n/e²)ⁿ. Until the present paper, no superexponential lower bound for T(n) was known. We also give a simpler proof of the upper bound.