Doctoral Degrees (Logistics)

Permanent URI for this collection

https://scholar.sun.ac.za/handle/10019.1/726

Browse

Browsing Doctoral Degrees (Logistics) by Author "Kidd, Martin Philip"

Now showing 1 - 1 of 1
  • Thumbnail Image
    Item
    On the existence and enumeration of sets of two or three mutually orthogonal Latin squares with application to sports tournament scheduling
    (Stellenbosch : Stellenbosch University, 2012-03) Kidd, Martin Philip; Van Vuuren, J. H.; Burger, A. P.; Stellenbosch University. Faculty of Economic and Management Sciences. Dept. of Logistics.
    ENGLISH ABSTRACT: A Latin square of order n is an n×n array containing an arrangement of n distinct symbols with the property that every row and every column of the array contains each symbol exactly once. It is well known that Latin squares may be used for the purpose of constructing designs which require a balanced arrangement of a set of elements subject to a number of strict constraints. An important application of Latin squares arises in the scheduling of various types of balanced sports tournaments, the simplest example of which is a so-called round-robin tournament — a tournament in which each team opposes each other team exactly once. Among the various applications of Latin squares to sports tournament scheduling, the problem of scheduling special types of mixed doubles tennis and table tennis tournaments using special sets of three mutually orthogonal Latin squares is of particular interest in this dissertation. A so-called mixed doubles table tennis (MDTT) tournament comprises two teams, both consisting of men and women, competing in a mixed doubles round-robin fashion, and it is known that any set of three mutually orthogonal Latin squares may be used to obtain a schedule for such a tournament. A more interesting sports tournament design, however, and one that has been sought by sports clubs in at least two reported cases, is known as a spouse-avoiding mixed doubles round-robin (SAMDRR) tournament, and it is known that such a tournament may be scheduled using a self-orthogonal Latin square with a symmetric orthogonal mate (SOLSSOM). These applications have given rise to a number of important unsolved problems in the theory of Latin squares, the most celebrated of which is the question of whether or not a set of three mutually orthogonal Latin squares of order 10 exists. Another open question is whether or not SOLSSOMs of orders 10 and 14 exist. A further problem in the theory of Latin squares that has received considerable attention in the literature is the problem of counting the number of (essentially) different ways in which a set of elements may be arranged to form a Latin square, i.e. the problem of enumerating Latin squares and equivalence classes of Latin squares of a given order. This problem quickly becomes extremely difficult as the order of the Latin square grows, and considerable computational power is often required for this purpose. In the literature on Latin squares only a small number of equivalence classes of self-orthogonal Latin squares (SOLS) have been enumerated, namely the number of distinct SOLS, the number of idempotent SOLS and the number of isomorphism classes generated by idempotent SOLS of orders 4 n 9. Furthermore, only a small number of equivalence classes of ordered sets of k mutually orthogonal Latin squares (k-MOLS) of order n have been enumerated in the literature, namely main classes of 2-MOLS of order n for 3 n 8 and isotopy classes of 8-MOLS of order 9. No enumeration work on SOLSSOMs appears in the literature. In this dissertation a methodology is presented for enumerating equivalence classes of Latin squares using a recursive, backtracking tree-search approach which attempts to eliminate redundancy in the search by only considering structures which have the potential to be completed to well-defined class representatives. This approach ensures that the enumeration algorithm only generates one Latin square from each of the classes to be enumerated, thus also generating a repository of class representatives of these classes. These class representatives may be used in conjunction with various well-known enumeration results from the theory of groups and group actions in order to determine the number of Latin squares in each class as well as the numbers of various kinds of subclasses of each class. This methodology is applied in order to enumerate various equivalence classes of SOLS and SOLSSOMs of orders up to and including order 10 and various equivalence classes of k-MOLS of orders up to and including order 8. The known numbers of distinct SOLS, idempotent SOLS and isomorphism classes generated by idempotent SOLS are verified for orders 4 n 9, and in addition the number of isomorphism classes, transpose-isomorphism classes and RC-paratopism classes of SOLS of these orders are enumerated. The search is further extended to determine the numbers of these classes for SOLS of order 10 via a large parallelisation of the backtracking treesearch algorithm on a number of processors. The RC-paratopism class representatives of SOLS thus generated are then utilised for the purpose of enumerating SOLSSOMs, while existing repositories of symmetric Latin squares are also used for this purpose as a means of validating the enumeration results. In this way distinct SOLSSOMs, standard SOLSSOMs, transposeisomorphism classes of SOLSSOMs and RC-paratopism classes of SOLSSOMs are enumerated, and a repository of RC-paratopism class representatives of SOLSSOMs is also produced. The known number of main classes of 2-MOLS of orders 3 n 8 are verified in this dissertation, and in addition the number of main classes of k-MOLS of orders 3 n 8 are also determined for 3 k n−1. Other equivalence classes of k-MOLS of order n that are enumerated include distinct k-MOLS and reduced k-MOLS of orders 3 n 8 for 2 k n − 1. Finally, a filtering method is employed to verify whether any SOLS of order 10 satisfies two basic necessary conditions for admitting a common orthogonal mate with its transpose, and it is found via a computer search that only four of the 121 642 class representatives of RC-paratopism classes of SOLS satisfy these conditions. It is further verified that none of these four SOLS admits a common orthogonal mate with its transpose. By this method the spectrum of resolved orders in terms of the existence of SOLSSOMs is improved in that the non-existence of such designs of order 10 is established, thereby resolving a longstanding open existence question in the theory of Latin squares. Furthermore, this result establishes a new necessary condition for the existence of a set of three mutually orthogonal Latin squares of order 10, namely that such a set cannot contain a SOLS and its transpose