Subsquares in random Latin rectangles
A Latin square of order \(n\) is an \(n\times n\) matrix with each position filled by a symbol from an \(n\)-element symbol set (usually \([n]=\{1,2,\ldots n\}\)) and each symbol appearing exactly once in each row and in each column. Somewhat more generally, a \(k\times n\) Latin rectangle with \(k\leq n\) is a \(k\times n\) matrix with each position filled by a symbol from an \(n\)-element set with each symbol appearing at most once in each row and in each column. (An \(n\times n\) Latin rectangle is indeed a Latin square).\par A Latin subsquare of order \(r\) of a Latin rectangle is a square \(r\times r\) submatrix which forms a Latin square (so all \(r^{2}\) entries in the submatrix are from some \(r\)-element subset of \([n]\) and each element appears once in each row and column. The rows and columns do not have to be consecutive in the original matrix). Every Latin square is a subsquare of itself, and it also has \(n^{2}\) subsquares of order 1; any other subsquares are proper subsquares. While the authors have shown elsewhere [``Latin squares without proper subsquares, Preprint, arXiv:2310.01923] that there are Latin squares of order \(n\) with no proper subsquares provided \(n\not \in \{4,6\}\), most Latin squares do have many proper subsquares (though informally many of them are order 2 subsquares (intercalates)); see e.g. \textit{B. D. McKay} and \textit{I. M. Wanless} [J. Comb. Theory, Ser. A 86, No. 2, 323--347 (1999; Zbl 0948.05014)]. The largest possible order of a proper Latin subsquare of an \(n\times n\) Latin square is easily seen to be \(n/2\).\N\NThe aim of the paper under review is to consider the number of subsquares of a random \(k\times n\) Latin rectangle. (Here, as usual, random means uniformly at random). For \(2\leq m\leq n/2\), and still with \(k\leq n\), let \(\mathbb{E}_{m}(k,n)\) be the expected number of \(m\times m\) Latin subsquares in a random \(k\times n\) Latin rectangle. The main result of the paper under review is that if \(m,k\) are integer functions of \(n\) with \(4\leq m\leq \min\{k,n/2\}\) then \(\mathbb{E}_{m}(k,n)=O(n^{-2})\) as \(n\) tends to infinity. In particular, with probability \(1-O(1/n)\) there is no proper subsquare of order 4 or more. Earlier work of various authors had shown that the number of intercalates has expected value \((1+o(1)) n^{2}/4\) and that (crudely summarising) large deviations from this mean are highly unlikely, see Theorem 2.1 in the paper under review for a precise statement. The situation for subsquares of order 3 is still not wholly clear, but it is shown that \(\mathbb{E}_{3}(k,n)=O(k/n)\) - McKay and Wanless [loc. cit.] conjectured that \(\mathbb{E}_{3}(n,n)=1/18+o(1)\). The authors also show that \(\mathbb{E}_{2}(k,n)=(1/2+o(1))\binom{k}{2}\).\par Proofs use the switching method to count substructures. Various upper bounds on the probability of an \(m\times m\) Latin subsquare are shown, different ones being more effective in particular ranges.
This page was built for publication: Subsquares in random Latin rectangles
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6952674)
