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