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

Abstract. We prove that for n ∈ N and an absolute constant C, if p ≥ C log2 n/n and Li,j ⊆ [n] is a random subset of [n] where each k ∈ [n] is included in Li,j independently with probability p for each i, j ∈ [n], then asymptotically almost surely there is an order-n Latin square in which the entry in the ith row and jth column lies in Li,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¨aggkvist [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.