Intercalates and discrepancy in random Latin squares

DOI10.1002/RSA.20742MaRDI QIDQ4564855zbMATH OpenOpenAlexFDO

Authors Matthew Kwan, Benny Sudakov

Publication date 7 June 2018

Published in Random Structures \& Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

discrepancyLatin squareintercalatelow-discrepancy Latin squares

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Orthogonal arrays, Latin squares, Room squares (05B15)

Abstract: An intercalate in a Latin square is a $2imes2$ Latin subsquare. Let $N$ be the number of intercalates in a uniformly random $nimesn$ Latin square. We prove that asymptotically almost surely $Ngeleft(1-oleft(1ight)ight),n^2/4$, and that $mathbbENleleft(1+oleft(1ight)ight),n^2/2$ (therefore asymptotically almost surely $Nlef{n}^2$ for any $foinfty$). This significantly improves the previous best lower and upper bounds. We also give an upper tail bound for the number of intercalates in two fixed rows of a random Latin square. In addition, we discuss a problem of Linial and Luria on low-discrepancy Latin squares.

Recommendations

• Large deviations in random latin squares
• Latin squares with bounded size of row prefix intersections
• Substructures in Latin squares
• Most Latin squares have many subsquares
• Quasirandom Latin squares

Cited in

(16)

• Uniform semi-Latin squares and their pairwise-variance aberrations
• Hamilton transversals in random Latin squares
• Random Latin squares and 2-dimensional expanders
• On the threshold problem for Latin boxes
• Discrepancy of high-dimensional permutations
• Substructures in Latin squares
• Latin squares and low discrepancy allocation of two-dimensional data
• Subsquares in random Latin squares and rectangles
• The degree-restricted random process is far from uniform
• Isotopisms of quadratic quasigroups
• Covers and partial transversals of Latin squares
• scientific article; zbMATH DE number 1744081 (Why is no real title available?)
• Almost all optimally coloured complete graphs contain a rainbow Hamilton path
• Almost all Steiner triple systems are almost resolvable
• The cycle structure of two rows in a random Latin square
• Large deviations in random latin squares

This page was built for publication: Intercalates and discrepancy in random Latin squares

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