On maximal partial Latin hypercubes

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 (Latin squares) and d= 3 (Latin cubes). Explicit constructions show that this bound is near-optimal for large n> d . For 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.