On maximal orthogonal partial Latin squares and minimal codes with specified length, minimum distance and covering radius

This paper presents a conjecture concerning the minimum possible size of a pair of maximal orthogonal partial Latin squares of a given order n. We show that in the balanced case the optimal structure is formed from a pair of partial Latin squares, each comprising three subsquares whose orders are as close as possible to one another and sum to n. Further results are obtained in unbalanced cases. The problem can be recast in terms of finding the minimum number of blocks in a maximal partial transversal design TD(4, n), and as finding the minimum number of codewords in an n-ary code of length 4 having minimum distance 3 and covering radius 2. The conjecture is extended to sets of k maximal mutually orthogonal partial Latin squares and hence to n-ary codes of length k+2, minimum distance k+1 and covering radius k.