- Series
- Graph Theory Seminar
- Time
- Tuesday, August 30, 2022 - 3:45pm for 1 hour (actually 50 minutes)
- Location
- Skiles 005
- Speaker
- Tom Kelly – Georgia Tech – tom.kelly@gatech.edu – https://tomkelly.math.gatech.edu
- Organizer
- Tom Kelly
An order-n Latin square is an $n \times n$ matrix with entries from a set of $n$ symbols, such that each row and each column contains each symbol exactly once. Suppose that $L_{i,j} \subseteq [n]$ is a random subset of $[n]$ where each $k \in [n]$ is included in $L_{i,j}$ independently with probability $p$ for each $i,j\in[n]$. How likely does there exist an order-$n$ Latin square where the entry in the $i$th row and $j$th column lies in $L_{i,j}$? This question was initially raised by Johansson in 2006, and later Casselgren and H{\"a}ggkvist and independently Luria and Simkin conjectured that $\log n / n$ is the threshold for this property. In joint work with Dong-yeap Kang, Daniela K\"{u}hn, Abhishek Methuku, and Deryk Osthus, we proved that for some absolute constant $C$, if $p > C \log^2 n / n$, then asymptotically almost surely there exists such a Latin square. We also prove analogous results for Steiner triple systems and $1$-factorizations of complete graphs.