The threshold problem for Latin squares

An order-$n$ Latin square is equivalent to a triangle-decomposition of the complete tripartite hypergraph $K_{n,n,n}$. Let $H \sim H_3(n,n,n;p)$ be a tripartite, balanced, binomial random $3$-uniform hypergraph on $3n$ vertices where each edge is present with probability $p$. What is the threshold $p$ for the property that $H$ contains a Latin square? The general heuristic is that spanning structures appear together with the disappearance of local obstructions. Thus the natural conjecture is $p = 2 \log(n) / n$, which corresponds to the disappearance of edges not contained in any triangle.

While this problem remains open, two natural approaches are to consider approximations of Latin squares, and to obtain (possibly suboptimal) upper bounds on the threshold probability. I will review results in both directions.

The lion's share of the talk will be spent discussing an application of Keevash's method of randomized algebraic construction to show an upper bound of $n^{-1/7+ o(1)}$ on the threshold probability.

Parts of the talk are the result of joint work with Zur Luria.