# 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)
n02chapter1.pdf Thesis (open access) application/pdf 51.94KB 0
n03chapter2.pdf Thesis (open access) application/pdf 142.12KB 0
n04chapter3.pdf Thesis (open access) application/pdf 154.37KB 0
n05chapter4.pdf Thesis (open access) application/pdf 103.93KB 0
n06chapter5.pdf Thesis (open access) application/pdf 143.95KB 0
n07chapter6.pdf Thesis (open access) application/pdf 90.56KB 0
n08chapter7.pdf Thesis (open access) application/pdf 128.55KB 0
n09chapter8.pdf Thesis (open access) application/pdf 134.68KB 0
n0front.pdf Thesis (open access) application/pdf 102.73KB 0
n10chapter9.pdf Thesis (open access) application/pdf 40.38KB 0
n11appendix.pdf Thesis (open access) application/pdf 101.70KB 0
n12references.pdf Thesis (open access) application/pdf 82.61KB 0
Author Bean, Richard Winston Critical Sets in Latin Squares and Associated Structures School of Physical Sciences The University of Queensland 10.14264/uql.2016.77 2001-01-01 PhD Thesis Diane Donovan 132 2001 eng 280401 Analysis of Algorithms and Complexity230101 Mathematical Logic, Set Theory, Lattices And Combinatorics280405 Discrete Mathematics780101 Mathematical sciences 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. Latin interchangesIntercalatesCombinatoricsSteiner tradesSteiner triple systemsAlgorithms

 Document type: Thesis UQ Theses (RHD) - Official UQ Theses (RHD) - Open Access

 Versions Version Filter Type Sat, 21 Jan 2017, 08:06:37 EST Filtered Full
Citation counts: Search Google Scholar Fri, 24 Oct 2008, 21:13:35 EST