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

Abstract

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$$ k + 2 , minimum distance $$k+1$$ k + 1 and covering radius k .