Combinatorics Seminar

When: Sunday, November 25, 10am
Where: Schreiber 309
Speaker: Michael Simkin, Hebrew University
Title: The threshold problem for Latin squares

Abstract:

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 corresp.onds 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.