Thresholds for latin squares and Steiner triple systems: Bounds within a logarithmic factor

Abstract:

We prove that for $n \in \mathbb N$ and an absolute constant $C$, if $p \geq C\log ^2 n / n$ and $L_{i,j} \subseteq [n]$ is a random subset of $[n]$ where each $k\in [n]$ is included in $L_{i,j}$ independently with probability $p$ for each $i, j\in [n]$, then asymptotically almost surely there is an order-$n$ Latin square in which the entry in the $i$th row and $j$th column lies in $L_{i,j}$. The problem of determining the threshold probability for the existence of an order-$n$ Latin square was raised independently by Johansson [Triangle factors in random graphs, 2006], by Luria and Simkin [Random Structures Algorithms 55 (2019), pp. 926–949], and by Casselgren and Häggkvist [Graphs Combin. 32 (2016), pp. 533–542]; our result provides an upper bound which is tight up to a factor of $\log n$ and strengthens the bound recently obtained by Sah, Sawhney, and Simkin [Threshold for Steiner triple systems, arXiv:2204.03964, 2022]. We also prove analogous results for Steiner triple systems and $1$-factorizations of complete graphs, and moreover, we show that each of these thresholds is at most the threshold for the existence of a $1$-factorization of a nearly complete regular bipartite graph.