Combinatorial Theory

Let \(L\) be an \(n\times n\) array whose top left \(r\times r\) subarray is filled with \(k\) different symbols, each occurring at most once in each row and at most once in each column. We establish necessary and sufficient conditions that ensure the remaining cells of \(L\) can be filled such that each symbol occurs at most once in each row and at most once in each column, \(L\) is symmetric with respect to the main diagonal, and each symbol occurs a prescribed number of times in \(L\). The case where the prescribed number of times each symbol occurs is \(n\) was solved by Cruse (J. Combin. Theory Ser. A 16 (1974), 18-22), and the case where the top left subarray is \(r\times n\) and the symmetry is not required, was settled by Goldwasser et al. (J. Combin. Theory Ser. A 130 (2015), 26-41). Our result allows the entries of the main diagonal to be specified as well, which leads to an extension of the Andersen-Hoffman Theorem (Annals of Disc. Math. 15 (1982) 9-26, European J. Combin. 4 (1983) 33-35).

Mathematics Subject Classifications: 05B15, 05C70, 05C15

Keywords: Latin square, embedding, \((g,f)\)-factors, Cruse's Theorem, Andersen-Hoffman's Theorem, Ryser's Theorem, amalgamation, detachment