Skip to main content

Mathematical Sciences-Discrete Mathematics Seminar- Ashwin Sah (MIT)-"Large Deviations in Random Latin Squares"

Monday, September 27, 2021
2:00 pm
Floor/Room #: 
via Zoom

Speaker: Ashwin Sah (MIT)
Title: "Large Deviations in Random Latin Squares"

Abstract: We study large deviations of the number N of intercalates (2 x 2 combinatorial subsquares which are themselves Latin squares) in a random n x n Latin square. In particular, for constant δ > 0 we prove that Pr(N ≤ (1-δ)n2/4 )≤ exp(-Ω(n2)) and Pr(N ≥ (1+δ)n2/4 )≤ exp(-Ω(n4/3(log n)2/3)) both of which are sharp up to logarithmic factors in their exponents. As a consequence, we deduce that a typical order-n Latin square has (1+o(1))n2/4 intercalates, matching a lower bound due to Kwan and Sudakov and resolving an old conjecture of McKay and Wanless.

This talk will be given via Zoom. Please contact Bill Martin for Zoom ID.