Combinatorics Seminar

When: Sunday, January 8, 10am
Where: Schreiber 309
Speaker: Zur Luria, ETH-ITS
Title: Some recent developments in the study of Latin squares


The past couple of years have seen several major results in the study of Latin squares.

A transversal in an order-n Latin square is a set of n elements, one from each row and column and one of each symbol. Let T(n) denote the maximal number of transversals that an order-n Latin square can have. In a joint work with Roman Glebov, we proved asymptotically tight upper and lower bounds on T(n), using probabilistic methods. More recent developments include an algebraic construction of Latin squares that achieve the lower bound. It was also shown that Keevash's recent construction of designs could be used to show that whp random Latin squares attain the lower bound.

The expander mixing lemma is concerned with the discrepancy of regular graphs. One can consider this parameter in higher dimensions as well, and in particular for Latin squares. In a joint work with Nati Linial, we conjectured that a typical Latin square has low discrepancy, and proved a related result. More recently, Kwan and Sudakov showed that a breakthrough result of Liebenau and Wormald on the enumeration of regular graphs implies our conjecture for Latin squares up to a multiplicative factor of log^2(n).

Many open questions remain.