Large deviations in random latin squares

DOI10.1112/BLMS.12638zbMATH Open1522.05020arXiv2106.11932OpenAlexW3175138403WikidataQ113270015 ScholiaQ113270015MaRDI QIDQ6133414FDOQ6133414

Authors: Matthew Kwan, Ashwin Sah, Mehtaab Sawhney 

Publication date: 18 August 2023

Published in: Bulletin of the London Mathematical Society (Search for Journal in Brave)

Abstract: In this note, we study large deviations of the number $mathbfN$ of intercalates ($2imes2$ combinatorial subsquares which are themselves Latin squares) in a random $nimesn$ Latin square. In particular, for constant $delta>0$ we prove that $Pr(mathbfNle(1-delta)n^2/4)leexp(-Omega(n^2))$ and $Pr(mathbfNge(1+delta)n^2/4)leexp(-Omega(n^{4/3}(logn{)}^{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))n^2/4$ intercalates, matching a lower bound due to Kwan and Sudakov and resolving an old conjecture of McKay and Wanless.

Full work available at URL: https://arxiv.org/abs/2106.11932

Recommendations

• Intercalates and discrepancy in random Latin squares
• Most Latin squares have many subsquares
• Substructures in Latin squares
• The cycle structure of two rows in a random Latin square
• Transversals in quasirandom latin squares
• Thresholds for Latin squares and Steiner triple systems: Bounds within a logarithmic factor
• Quasirandom Latin squares
• On the threshold problem for Latin boxes
• Asymptotic enumeration of generalized Latin rectangles

zbMATH Keywords

Latin squaresLatin rectangleintercalate3-partite 3-uniform hypergraphs

Mathematics Subject Classification ID

Large deviations (60F10) Random graphs (graph-theoretic aspects) (05C80) Orthogonal arrays, Latin squares, Room squares (05B15)

Cites Work

• On tail probabilities for martingales
• A course in combinatorics.
• On the number of Latin squares
• Counting designs
• Transversals in Latin squares: a survey
• An upper bound on the number of high-dimensional permutations
• The Littlewood-Offord problem and invertibility of random matrices
• Title not available (Why is that?)
• Title not available (Why is that?)
• Generating uniformly distributed random latin squares
• The chromatic number of random graphs
• Asymptotic enumeration of Latin rectangles
• Proof of the van der Waerden conjecture regarding the permanent of a doubly stochastic matrix
• Threshold Functions for Ramsey Properties
• The deletion method for upper tail estimates
• The missing log in large deviations for triangle counts
• The infamous upper tail
• The cycle structure of two rows in a random Latin square
• Mappings of Latin squares
• Title not available (Why is that?)
• Upper tail for homomorphism counts in constrained sparse random graphs
• The solution of van der Waerden's problem for permanents
• Intercalates and discrepancy in random Latin squares
• Upper tails for triangles
• Most Latin squares have many subsquares
• Almost All Steiner Triple Systems Are Asymmetric
• Combinatorial estimates by the switching method
• Title not available (Why is that?)
• Title not available (Why is that?)
• All-even Latin squares
• Almost all quasigroups have rank 2
• Random triangle removal
• Monotone subsequences in high-dimensional permutations
• On certain constructions for latin squares with no latin subsquares of order two
• Title not available (Why is that?)
• Title not available (Why is that?)
• Discrepancy of high-dimensional permutations
• Upper tails and independence polynomials in random graphs
• Almost all Steiner triple systems are almost resolvable
• Large deviations of subgraph counts for sparse Erdős-Rényi graphs
• Nonlinear large deviation bounds with applications to Wigner matrices and sparse Erdős-Rényi graphs
• Upper tails via high moments and entropic stability
• Almost all Steiner triple systems have perfect matchings
• Minimalist designs
• Bounds on the number of small Latin subsquares
• HYPERGRAPH MATCHINGS AND DESIGNS

Cited In (12)

• Uniform semi-Latin squares and their pairwise-variance aberrations
• Hamilton transversals in random Latin squares
• Row‐Hamiltonian Latin squares and Falconer varieties
• Random Latin squares and 2-dimensional expanders
• On the threshold problem for Latin boxes
• Discrepancy of high-dimensional permutations
• Substructures in Latin squares
• Threshold for Steiner triple systems
• Stochastic scrabble: large deviations for sequences with scores
• Intercalates and discrepancy in random Latin squares
• The cycle structure of two rows in a random Latin square
• Cycles of quadratic Latin squares and antiperfect 1‐factorisations

This page was built for publication: Large deviations in random latin squares

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6133414)