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. doi:10.14264/uql.2016.77

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

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
DOI 10.14264/uql.2016.77
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
Steiner trades
Steiner triple systems

Document type: Thesis
Collections: UQ Theses (RHD) - Official
UQ Theses (RHD) - Open Access
Version Filter Type
Citation counts: Google Scholar Search Google Scholar
Created: Fri, 21 Nov 2008, 20:44:10 EST