Talk information

Date: Sunday, April 27, 2025
Time: 10:10–11:00
Place: Schreiber 309
Speaker: Micha Christoph (ETH Zurich)
Title: Almost-full transversals in equi-$n$-squares

Abstract:

A Latin square is an $n\times n$ array filled with $n$ symbols where each symbol appears exactly once in each row and column. In a recent breakthrough, Montgomery showed that every Latin square has a transversal of size $n-1$. That is, it should have a collection of $n-1$ entries that share no row, column, or symbol. In 1975, Stein conjectured a wide generalization of the above result, stating that every equi-$n$-square (an $n\times n$ array filled with $n$ symbols where each symbol appears exactly $n$ times) has a transversal of size $n-1$. While this ambitious conjecture is known to be false, I will present a proof that every equi-$n$-square has a transversal of size $n-n^{1-\Omega(1)}$ as well as a short proof that this is tight up to the $\Omega(1)$.

Joint work with Chakraborti, Hunter, Montgomery and Petrov.