On maximal partial Latin hypercubes

Donovan, Diane. M.; Grannell, Mike J. and Yazici, Emine. Sule (2023). On maximal partial Latin hypercubes. Designs, Codes and Cryptography (Early access).


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

Viewing alternatives

Download history

Item Actions