Joint CS-Math Seminar
Time: 2 pm to 3:15 pm
Venue: Seminar Hall
Existence of transversal in a Latin rectangle
The Institute for Basic Sciences, 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. 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