An approximate version of Brualdi-Ryser-Stein conjecture

Wednesday, October 6, 2021 - 3:30pm to 4:30pm
Virtual via Zoom


Debsoumya Chakraborti
Postdoctoral Researcher
Institute for Basic Science (IBS), South Korea


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.  


Discrete Math Seminar
Wednesday, October 6, 2021
3:30pm MST/AZ
Password: 692054


Event Type

COVID 19 Information

COVID-19 information