Quasirandom Latin squares

2020/11/15 by Jacob W. Cooper, Cooper, Jacob W., Daniel Kral +5
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #math.CO

paper · pdf · doi:10.48550/arxiv.2011.07572

arxiv created 2021/08/25 · arxiv updated 2021/08/27

Abstract

We prove a conjecture by Garbe et al. [arXiv:2010.07854] by showing that a Latin square is quasirandom if and only if the density of every 2x3 pattern is 1/720+o(1). This result is the best possible in the sense that 2x3 cannot be replaced with 2x2 or 1xN for any N.

Related

• Completions of epsilon-dense partial Latin squares; quasirandom k-colorings of graphs
• Canonical labelling of Latin squares in average-case polynomial time
• Almost every Latin square has a decomposition into transversals
• Substructures in Latin squares
• Large deviations in random Latin squares