The threshold problem for Latin squares

Seminar
Speaker
Michael Simkin (Hebrew University of Jerusalem)
Date
18/11/2018 - 15:30 - 14:00Add to Calendar 2018-11-18 14:00:00 2018-11-18 15:30:00 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. Room 201, Math and CS Building (Bldg. 216) אוניברסיטת בר-אילן - Department of Mathematics mathoffice@math.biu.ac.il Asia/Jerusalem public
Place
Room 201, Math and CS Building (Bldg. 216)
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 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.

Last Updated Date : 14/11/2018