Critical Sets in Latin Squares and Associated Structures

Bean, Richard Winston (2001). Critical Sets in Latin Squares and Associated Structures PhD Thesis, School of Physical Sciences, The University of Queensland.

Attached Files (Some files may be inaccessible until you login with your UQ eSpace credentials)
Name Description MIMEType Size Downloads
n02chapter1.pdf n02chapter1.pdf application/pdf 51.94KB 0
n03chapter2.pdf n03chapter2.pdf application/pdf 142.12KB 0
n04chapter3.pdf n04chapter3.pdf application/pdf 154.37KB 0
n05chapter4.pdf n05chapter4.pdf application/pdf 103.93KB 0
n06chapter5.pdf n06chapter5.pdf application/pdf 143.95KB 0
n07chapter6.pdf n07chapter6.pdf application/pdf 90.56KB 0
n08chapter7.pdf n08chapter7.pdf application/pdf 128.55KB 0
n09chapter8.pdf n09chapter8.pdf application/pdf 134.68KB 0
n0front.pdf Full thesis (Author verison) application/pdf 102.73KB 188
n10chapter9.pdf n10chapter9.pdf application/pdf 40.38KB 0
n11appendix.pdf n11appendix.pdf application/pdf 101.70KB 0
n12references.pdf n12references.pdf application/pdf 82.61KB 0

Author Bean, Richard Winston
Thesis Title Critical Sets in Latin Squares and Associated Structures
School, Centre or Institute School of Physical Sciences
Institution The University of Queensland
Publication date 2001
Thesis type PhD Thesis
Supervisor Diane Donovan
Total pages 132
Collection year 2001
Language eng
Subjects 280401 Analysis of Algorithms and Complexity
230101 Mathematical Logic, Set Theory, Lattices And Combinatorics
280405 Discrete Mathematics
780101 Mathematical sciences
Abstract/Summary A critical set in a Latin square of order n is a set of entries in an n×n array which can be embedded in precisely one Latin square of order n, with the property that if any entry of the critical set is deleted, the remaining set can be embedded in more than one Latin square of order n. The number of critical sets grows super-exponentially as the order of the Latin square increases. It is difficult to find patterns in Latin squares of small order (order 5 or less) which can be generalised in the process of creating new theorems. Thus, I have written many algorithms to find critical sets with various properties in Latin squares of order greater than 5, and to deal with other related structures. Some algorithms used in the body of the thesis are presented in Chapter 3; results which arise from the computational studies and observations of the patterns and subsequent results are presented in Chapters 4, 5, 6, 7 and 8. The cardinality of the largest critical set in any Latin square of order n is denoted by lcs(n). In 1978 Curran and van Rees proved that lcs(n)<=n²-n. In Chapter 4, it is shown that lcs(n)<=n²-3n+3. Chapter 5 provides new bounds on the maximum number of intercalates in Latin squares of orders m×2^α (m odd, α>=2) and m×2^α+1 (m odd, α>=2 and α≠3), and a new lower bound on lcs(4m). It also discusses critical sets in intercalate-rich Latin squares of orders 11 and 14. In Chapter 6 a construction is given which verifies the existence of a critical set of size n²÷ 4 + 1 when n is even and n>=6. The construction is based on the discovery of a critical set of size 17 for a Latin square of order 8. In Chapter 7 the representation of Steiner trades of volume less than or equal to nine is examined. Computational results are used to identify those trades for which the associated partial Latin square can be decomposed into six disjoint Latin interchanges. Chapter 8 focusses on critical sets in Latin squares of order at most six and extensive computational routines are used to identify all the critical sets of different sizes in these Latin squares.
Keyword Latin interchanges
intercalates
combinatorics
Steiner trades
Steiner triple systems
algorithms
 
Access Statistics: 164 Abstract Views, 189 File Downloads  -  Detailed Statistics
Created: Fri, 21 Nov 2008, 20:44:10 EST  -  Detailed History