Embedding partial Latin squares in Latin squares with many mutually orthogonal mates

Abstract

In this paper it is shown that any partial Latin square of order n can be embedded in a Latin square of order at most 16n2 which has at least 2n mutually orthogonal mates. Further, for any t⩾2, it is shown that a pair of orthogonal partial Latin squares of order n can be embedded in a set of t mutually orthogonal Latin squares (MOLS) of order a polynomial with respect to n. A consequence of the constructions is that, if N(n) denotes the size of the largest set of MOLS of order n, then N(n2)⩾N(n)+2. In particular, it follows that N(576)⩾9, improving the previously known lower bound N(576)⩾8.