Joint CS-Math Seminar
Date: 23/05/2022
Day: Monday
Time: 2 pm to 3:15 pm
Venue: Seminar Hall
Existence of transversal in a Latin rectangle
Debsoumya Chakraborti
The Institute for Basic Sciences, South Korea.
23-05-22

---

Abstract

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. Transversals in Latin squares have been a classical research topic in combinatorics, dating back to the time of Euler, who studied conditions on when Latin squares can be decomposed into transversals. One of the central and long-standing conjectures in combinatorial design, 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 (analogously defined as a Latin square where the number of rows and columns can differ) of size $n \times (n+o(n))$, 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. This talk will be based on joint work with Po-Shen Loh.