Critical sets of full Latin squares

Abstract

This thesis explores the properties of critical sets of the full n-Latin square and related combinatorial structures including full designs, (m,n,2)-balanced Latin rectangles and n-Latin cubes.

In Chapter 3 we study known results on designs and the analogies between critical sets of the full n-Latin square and minimal defining sets of the full designs.

Next in Chapter 4 we fully classify the critical sets of the full (m,n,2)-balanced Latin square, by describing the precise structures of these critical sets from the smallest to the largest.

Properties of different types of critical sets of the full n-Latin square are investigated in Chapter 5. We fully classify the structure of any saturated critical set of the full n-Latin square. We show in Theorem 5.8 that such a critical set has size exactly equal to n³ - 2n² - n. In Section 5.2 we give a construction which provides an upper bound for the size of the smallest critical set of the full n-Latin square. Similarly in Section 5.4, another construction gives a lower bound for the size of the largest non-saturated critical set. We conjecture that these bounds are best possible.

Using the results from Chapter 5, we obtain spectrum results on critical sets of the full n-Latin square in Chapter 6. In particular, we show that a critical set of each size between (n - 1)³ + 1 and n(n - 1)² + n - 2 exists.

In Chapter 7, we turn our focus to the completability of partial k-Latin squares. The relationship between partial k-Latin squares and semi-k-Latin squares is used to show that any partial k-Latin square of order n with at most (n - 1) non-empty cells is completable.

As Latin cubes generalize Latin squares, we attempt to generalize some of the results we have established on k-Latin squares so that they apply to k-Latin cubes. These results are presented in Chapter 8.