Atlantic Graph Theory Seminar

Date and Time: Wednesday, November 5, 3.40 pm Atlantic time

Speaker: Kalina Petrova, Institute of Science and Technology Austria

Title: Cameron’s conjecture on random Latin squares

Abstract: A conjecture of Cameron states that the distribution of the number of odd rows in an n x n uniformly random Latin square is approximately binomial with n trials and success probability 1/2. We prove this conjecture in several different senses, including total variation convergence, a local central limit theorem, and a large deviation principle. In fact, we prove a generalisation for the joint distribution of the number of odd rows, odd columns and odd symbols, showing they behave roughly as independent binomials. Along the way, we introduce several general techniques for the study of random Latin squares, including a new re-randomisation technique via “stable intercalate switchings”, and a new approximation theorem comparing random Latin squares with a certain independent model.
This is joint work with Matthew Kwan and Mehtaab Sawhney.