Large deviations in random latin squares

DOI10.1112/BLMS.12638MaRDI QIDQ6133414zbMATH OpenOpenAlexWikidataFDO

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)

Copyright license Creative Commons Attribution-NonCommercial 4.0 International

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

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)

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.

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

Cites work

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

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
• Discrepancy of high-dimensional permutations
• Random Latin squares and 2-dimensional expanders
• Substructures in Latin squares
• The cycle structure of two rows in a random Latin square
• Cycles of quadratic Latin squares and antiperfect 1‐factorisations
• Intercalates and discrepancy in random Latin squares
• Stochastic scrabble: large deviations for sequences with scores
• Threshold for Steiner triple systems
• On the threshold problem for Latin boxes

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)