An approximate version of Brualdi-Ryser-Stein conjecture

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

Speaker

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

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. 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.  

Description

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

share:


Event Type

COVID 19 Information

COVID-19 information
Success