Rutgers Discrete Mathematics Seminar

Title: Latin Square and Rainbow Structures

Speaker: Alexey Pokrovskiy, ETH Zurich

Date: Friday, December 9, 2016 2:15 pm

Location: Hill Center, Room 705, Rutgers University, Busch Campus, Piscataway, NJ


This talk will be about transversals in Latin squares. A Latin square of order n is an n x n array filled with n symbols such that no symbol appears twice in the same row or column. Latin squares are classic objects introduced in the 18th century by Euler. Since then, they have found applications in group theory, coding theory, and the design of experiments.

A transversal in a Latin square is a set of entries no two of which share the same row, column, or symbol. In the 60s, conjectures arose about Latin squares having large transversals. Ryser conjectured that for odd n, every order n Latin square has a size n transversal. Brualdi and Stein conjectured that every Latin square has a size n - 1 transversal. This talk will focus on developing methods to approach the difficult Ryser-Brualdi-Stein Conjectures. In particular proofs will be discussed of approximate versions of two variants of the Ryser-Brualdi-Stein Conjectures - the Aharoni-Berger Conjecture and Andersen's Conjecture concerning rainbow structures in graphs.