An approximate version of Brualdi-Ryser-Stein conjecture
A Latin square of order $n$ is an $n \times n$ array of $n$ symbols in which each symbol occurs exactly once in each row and column. A transversal of such a square is a set of $n$ entries such that no two entries share the same row, column, or symbol. One of the central and longstanding conjectures in combinatorial design, which is attributed to Brualdi, Ryser, and Stein, states that every $n \times n$ Latin square has a partial transversal of size $n-1$. We show the existence of a transversal of size $n$ in every Latin rectangle of size $n \times \left(n+o(n)\right)$, attaining a new asymptotic version of this conjecture. We further provide an efficient randomized algorithm to obtain one such transversal. We achieve this by analyzing a semi-random process using the differential equation method combined with the so-called nibble technique. This talk will be based on a joint work with Po-Shen Loh.