Latin squares with one subsquare
A subsquare of a Latin square is a submatrix which is itself a Latin square. A subsquare of a Latin square of order \(n\) is proper if its order \(m\) satisfies \(1<m<n\). A Latin square without any proper subsquares is said to be \(N_\infty\). This paper is a continuation of the quest to completely determine the spectrum of \(N_\infty\) Latin squares. The best general result in this area to date is that of \textit{L. D. Andersen} and \textit{E. Mendelsohn} in [A direct construction for Latin squares without proper subsquares, Ann. Discrete Math. 15, 27-53 (1982; Zbl 0493.05006)] who give a construction for \(N_\infty\) Latin squares of orders not of the form \(2^a3^b\). The rationale in this paper is to examine methods for constructing Latin squares which have exactly one subsquare (this class is called \(\mathcal{U}\)), and to then apply a small perturbation to destroy the existing subsquare. This idea was used by the author in his PhD thesis (Australian National University, 1997) to create \(N_\infty\) squares of orders \(32\), \(64\) and \(128\). In fact the author extended this idea to construct \(N_\infty\) squares for all previously unknown orders of the form \(2^a3^b < 256\). Two classes of Latin squares in \(\mathcal{U}\) are examined here. The first class consists of squares obtained by a prolongation of a skip square using transversals of a particular form. This class includes known squares due to \textit{M. McLeish} in [A direct construction of Latin squares with no subsquares of order two, Ars Comb. 10, 179-186 (1980; Zbl 0466.05013)] and to \textit{A. Kotzig} and \textit{J. Turgeon} [On certain constructions for Latin squares with no Latin subsquares of order two, Discrete Math. 16, 263-270 (1976; Zbl 0351.05016)]. The author prescribes conditions under which the resulting square belongs to \(\mathcal{U}\). In particular he shows that the order \(m\) of the proper subsquare of a Latin square of order \(n\) in \(\mathcal{U}\) must satisfy \(2m+1 \leq n\), and that this bound is tight. The second class of Latin squares in \(\mathcal{U}\) involves embedding a unique subsquare of order \(m\) in a Latin square of order \(km\) for a fixed integer \(k\). The resulting square is called a corrupted product, and relies on the identification of a so-called strong corrupting pair of \(N_{\infty}\) squares of order \(k\). The author finds strong corrupting pairs of order \(n\) for all \(n \leq 23\) and describes conditions under which the corrupted product belongs to \(\mathcal{U}\). The author foreshadows a systematic use of these techniques to completely resolve the existence question for \(N_{\infty}\) squares.
scientific article