Global ETD Search

Return to search

On Defining Sets in Latin Squares and two Intersection Problems, one for Latin Squares and one for Steiner Triple Systems

Consider distinct latin squares, L and M, of order n. Then the pair (T1, T2) where T1 = L \M and T2 = M \ L is called a latin bitrade. Furthermore T1 and T2 are referred to as latin trades, in which T2 is said to be a disjoint mate of T1 (and vice versa). Drápal (1991) showed that, under certain conditions, a partition of an equilateral triangle of side length n, where n is some integer, into smaller, integer length sided equilateral triangles gives rise to a latin trade within the latin square based on the addition table for the integers modulo n. A partial latin square P of order n is said to be completable if there exists a latin square L of order n such that P ⊆ L. If there is only one such possible latin square, L, of order n then P is said to be uniquely completable and P is called a defining set of L. Furthermore, if C is a uniquely completable partial latin square such that no proper subset of C is uniquely completable, C is said to be a critical set or a minimal defining set. These concepts, namely latin trades and defining sets in latin squares, are intimately connected by the following observation. If L is a latin square and D ⊆ L is a defining set, then D intersects all latin bitrades for which one mate is contained in L. In Part I of this thesis Dr´apal’s result is applied to investigate the structure of certain defining sets in latin squares. The results that are obtained are interesting in themselves; furthermore, the geometric approach to the problem yields additional appealing results. These geometric results are discussed in Chapters 3, 4, 5 and 6. They pertain to partitioning regions (polygons in R2 that satisfy certain obvious conditions) into equilateral, integer length sided, triangles, such that no point, in the region, is a corner of more than three distinct triangles. In Chapter 2 one of the main two theorems on defining sets is established, as is a method for using the above geometric results to prove the nonexistence of certain types of defining sets. In Part II of this thesis, intersection problems, for latin squares and Steiner triple systems, are considered. The seminal works, for problems of these types, are due to Lindner and Rosa (1975) and Fu (1980). A natural progression, from the established literature, for intersection problems between elements in a pair of latin squares or Steiner triple systems is to problems in which the intersection is composed of a number of disjoint configurations (isomorphic copies of some specified partial triple system). In this thesis solutions to two intersection problems for disjoint configurations are detailed. An m-flower, (F,F), is a partial triple system/configuration, such that: F = {{x, yi, zi} | {yi, zi} ∩ {yj , zj} = ∅, for 0 ≤ i, j ≤ m − 1, i 6= j}; and F = UX∈FX. The first such problem considered in this thesis asks for necessary and sufficient conditions for integers k and m ≥ 2 such that a pair of latin squares of order n exists that intersect precisely in k disjoint m-flowers. The necessary terminology, constructions, lemmas and proof for this result are contained in Chapters 7, 8 and 9. The second such problem considered in this thesis asks for necessary and sufficient conditions for integers k such that a pair of Steiner triple systems of order u exists that intersect precisely in k disjoint 2-flowers. This result relies on the solution to the latin square problem and an additional result from Chapter 9. The further constructions and lemmas used to prove this result are detailed in Chapter 10.