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 .

Abstract A lower bound is presented for the minimal number of filled cells in a maximal partial Latin hypercube of dimension d and order n. The result generalises and extends previous results for $$d=2$$ d = 2 (Latin squares) and $$d=3$$ d = 3 (Latin cubes). Explicit constructions show that this bound is near-optimal for large $$n> d$$ n > d . For $$d>n$$ d > n , a connection with Hamming codes shows that this lower bound gives a related upper bound for the same quantity. The results can be interpreted in terms of independent dominating sets in certain graphs, and in terms of codes that have covering radius 1 and minimum distance at least 2.