Almost every Latin square has a decomposition into transversals

Abstract

In 1782, Euler conjectured that no Latin square of order $n\equiv 2\text{mod}4$ has a decomposition into transversals. While confirmed for $n=6$ by Tarry in 1900, Bose, Parker, and Shrikhande constructed counterexamples in 1960 for each $n\equiv 2\text{mod}4$ with $n\ge 10$. We show that, in fact, counterexamples are extremely common, by showing that if a Latin square of order $n$ is chosen uniformly at random then with high probability it has a decomposition into transversals.

93 pages, 9 figures