Non-extendable partial Latin Hypercubes and Maximal orthogonal partial Latin Squares

Speaker: Professor E. Sule Yazıcı 
Affiliation: Koc¸ University

Abstract

A Latin hypercube is a generalisation of a Latin square to higher dimensions. A maximal or non-extendable partial Latin hypercube is a partial Latin Hypercube that cannot be extended to another partial Latin Hypercube with more filled cells by inserting any element of the entry set into any empty cell. 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. We will also present the close relation of non-extendable partial Latin hypercubes to independent dominating sets in certain graphs, and codes that have covering radius 1 and minimum distance at least 2. We will also introduce maximal orthogonal partial Latin squares,the structures whose classification is crucial for improving bounds for embeddings of orthogonal partial Latin squares. We will present some examples of these structures and a conjecture for the smallest possible number of filled cells in a pair of maximal orthogonal partial Latin squares.