Optimal thresholds for Latin squares, Steiner Triple Systems, and edge colorings

Abstract

We show that the threshold for the binomial random $3$-partite, $3$-uniform hypergraph $G^3((n,n,n),p)$ to contain a Latin square is $\Theta (\log n/n)$. We also prove analogous results for Steiner triple systems and proper list edge-colorings of the complete (bipartite) graph with random lists. Our results answer several related questions of Johansson, Luria-Simkin, Casselgren-Häggkvist, Simkin, and Kang-Kelly-Kühn-Methuku-Osthus.

arXiv comment10 pages. Simplified proof; results unchanged