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

Given a graph G, a random (k, n)-list assignment L for edges of G is an assignment of an independent, uniformly random set L(e) ∈ ([n]/k)of colors to each edge e and a proper L-list coloring of G is a proper edge-coloring where the color of an edge e belongs to L(e). We show that for a random (O(log n), n)-list assignment L for edges of the complete bipartite graph K_n,n, there is a an L-list coloring of K_n,n with high probability. We also prove analogous results for the thresholds of Steiner triple systems and Latin squares in random (binomial) hypergraphs. All of our results are optimal up to absolute constants, and resolve several related conjectures of Johansson, Luria-Simkin, Casselgren-Häggkvist, Simkin, and Kang-Kelly-Kühn-Methuku-Osthus.

 

A key contribution of our work is to show that in natural settings, the Lovász Local Lemma - a central tool in probabilistic combinatorics to establish the existence of objects with desired properties - can also be used to design optimally “spread” distributions on such objects. This is made possible by carefully exploiting the local uniformity property of the so-called Lovász Local Lemma distribution, an important observation that has recently been utilized in finding efficient algorithms for sampling approximately uniformly random solutions to constraint satisfaction problems. In conjunction with the recently proved Kahn-Kalai conjecture, this opens the door to obtaining optimal threshold results for the appearance of many interesting objects.