pith. sign in

arxiv: 2311.04152 · v2 · pith:HRMRERLNnew · submitted 2023-11-07 · 🧮 math.CO

Subsquares in random Latin squares and rectangles

classification 🧮 math.CO
keywords latinrandomrectangletimesbetaentriesnonemptypartial
0
0 comments X
read the original abstract

A $k \times n$ partial Latin rectangle is \textit{$C$-sparse} if the number of nonempty entries in each row and column is at most $C$ and each symbol is used at most $C$ times. We prove that the probability a uniformly random $k \times n$ Latin rectangle, where $k < (1/2 - \alpha)n$, contains a $\beta n$-sparse partial Latin rectangle with $\ell$ nonempty entries is $(\frac{1 \pm \varepsilon}{n})^\ell$ for sufficiently large $n$ and sufficiently small $\beta$. Using this result, we prove that a uniformly random order-$n$ Latin square asymptotically almost surely has no Latin subsquare of order greater than $c\sqrt{n\log n}$ for an absolute constant $c$.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.