Britz, T., Cavenagh, N. J., & Sørensen, H. K. (2015). Maximal partial Latin cubes. Electronic Journal of Combinatorics, 22(1).
Permanent Research Commons link: https://hdl.handle.net/10289/9306
We prove that each maximal partial Latin cube must have more than 29.289% of its cells filled and show by construction that this is a nearly tight bound. We also prove upper and lower bounds on the number of cells containing a fixed symbol in maximal partial Latin cubes and hypercubes, and we use these bounds to determine for small orders n the numbers k for which there exists a maximal partial Latin cube of order n with exactly k entries. Finally, we prove that maximal partial Latin cubes of order n exist of each size from approximately half-full (n3/2 for even n ≥ 10 and (n3 + n)/2 for odd n ≥21) to completely full, except for when either precisely 1 or 2 cells are empty.
Electronic Journal of Combinatorics
© 2015 the authors