Transversals, indivisible plexes and partitions of latin squares
Abstract
A k-plex in a latin square of order n is a selection of kn entries in which each row, column and symbol occurs exactly k times. A 1-plex is also called a transversal. A k-plex is indivisible if it contains no c-plex for 0 < c < k. Two or more plexes are parallel if no two of them share an entry. This thesis is the ï¬rst ma jor study giving general results on indivisible k-plexes for k > 1. For n ̸∈ {2, 6}, the existence of a latin square of order n with a partition into 1- plexes was shown by Bose, Shrikhande and Parker [1]. A natural extension of the result to k-plexes is the following. We prove that if k is a proper divisor of n, then there exists a latin square of order n composed of parallel indivisible k-plexes. Deï¬ne κ(n) to be the largest integer k such that some latin square of order n contains an indivisible k-plex. A conjecture by Rodney [3, p143] says that every latin square contains a 2-plex, which implies that κ(n) < n for all n > 2. We show that for all n > 2, there exists a latin square of order n with two parallel indivisible ⌊ n 2 ⌋-plexes. A corollary is that κ(n) ≥ ⌊ n 2 ⌋ for all n > 2. We report on extensive computations of the indivisible partitions of the latin squares of order n ≤ 9. Up to order 8 we count the number of indivisible partitions of every type. Due to Bose, Shrikhande and Parker [1], and Finney [10] for n = 6, we know that there exists a latin square for each order n > 2 which possesses a k-plex for all 0 ≤ k ≤ n. Wanless [12] showed that there are latin squares of every even order which contain no odd plexes, where an odd plex is a k-plex such that k is odd. It has been conjectured by Rodney [4], and by Wanless [12], that every latin square has a set of ⌊ n 2 ⌋ parallel 2-plexes which implies that every latin square of odd order has a k-plex for each 0 ≤ k ≤ n. We show that among the latin squares of even order there are many other possibilities concerning the existence of odd k-plexes. 1 We prove that for all even n > 2, there exists a latin square of order n which has no k-plex for any odd k < ⌊ n 4 ⌋, but does have a k-plex for every other k ≤ 1 2 n. A result by Wanless and Webb [13] is that, for all n > 3, there exists a latin square of order n with at least one entry not in any transversal. Such a latin square is called a conï¬rmed bachelor and illustrates a restriction on the transversals in a latin square. In our study of transversals we consider bachelor latin squares in greater detail and other types of restrictions that might occur. We give a concise alternative proof of the result by Wanless and Webb. A main result is that for all even n ≥ 10, except perhaps if n is a power of 2, there exists a latin square of order n that possesses a transversal, but every transversal coincides on a single entry. A theorem by Wanless, which was prompted by our data, shows that there exist arbitrarily large latin squares of odd order in which the proportion of entries not in a transversal is asymptotic to one ninth. We report on computations of parallel transversals in the latin squares of order 9. Thus we prove that the above mentioned conjectures by Rodney and Wanless are true for order 9, and that every latin square of order 9 has at least 3 parallel transversals. Our computations suggest that the constructions which prove our theorems illustrate rare behaviour in large latin squares. The computations also give further evidence in support of a conjecture by Ryser [11] (see [3, p143]) that every latin square of odd order has a transversal. Many of the theorems in this thesis rely on a simple but powerful lemma [6, 9]. The lemma gives a necessary condition for the existence of k-plexes. To show the existence of k-plexes we use constructive techniques. It remains open to establish a sufficient condition for the existence of k-plexes in latin squares. The main results of this thesis can be found in [2, 5–8]. Keywords : latin square, transversal, plex, duplex, triplex, quadruplex, indivisible plex, indivisible partition, orthogonal partition, bachelor square, mutually orthogo- nal latin squares, partial latin square, protoplex, homogeneous partial latin square, latin trade, homogeneous latin trade, rainbow factor, graph factorisation, quasi- group, complete mapping, orthomorphism.Published
2011-10-19
Issue
Section
Abstracts of PhD Theses
In these notes, the Australian Mathematical Publishing Association Incorporated, Cambridge Journals Online, Cambridge University Press, and the Bulletin are abbreviated to AMPAI, CJO, CUP, and the Bulletin.
Copyright is held by AMPAI. Under the standard arrangement, the article will be made freely accessible to the public five (5) years after publication. Alternatively, for an initial fee of $USD600, immediate open access under a creative commons license will be provided on the CUP online platform.
- The Bulletin's policy is to acquire copyright for as many articles as possible, for two reasons:
- ownership of copyright by one central organisation tends to ensure maximum international protection against unauthorised use;
- it also ensures that requests by third parties to reprint or reproduce a contribution, or part of it, are handled efficiently and in accordance with a general policy that is sensitive both to any relevant changes in international copyright legislation and to the general desirability of encouraging the dissemination of knowledge.
- Copyright acts in various countries confer 'moral rights' on authors. In some cases, an author's 'right of paternity', that is the right to be properly credited whenever the work is published (or performed or broadcast), must be asserted in writing.
- Notwithstanding the assignment of copyright in their contribution, all authors retain the following non-transferable rights:
- The right to post the abstract and a link to the online edition of the Bulletin at CJO or at the Bulletin website.
- The right to post the definitive version of the contribution as published at CJO (in PDF or HTML) in the Institutional Repository of the institution in which they worked at the time the paper was first submitted, no sooner than two years after first publication of the paper in the journal, subject to file availability and provided the posting includes a prominent statement of the full bibliographical details, a copyright notice in the name of the copyright holder (AMPAI or another body, as appropriate), and a link to the online edition of the Bulletin at CJO. Inclusion of this definitive version after two years in Institutional Repositories outside of the institution in which the author worked at the time the paper was first submitted will be subject to the additional permission of CUP on behalf of AMPAI (not to be unreasonably withheld).
- The right to make hard copies of the article or an adapted version for their own purposes, including the right to make multiple copies for course use by their students, provided no sale is involved.
- The right to reproduce the paper or an adapted version of it in any volume of which they are an editor or an author, but otherwise permission must be sought from CUP. Permission will automatically be given to the publisher of such a volume, subject to normal acknowledgement.
- CUP (on behalf of AMPAI) will use its best endeavours to ensure that any direct request received to reproduce a contribution, or a substantial part of it, in another publication (which may be an electronic publication) is approved by the contributor before permission is given. Multiple authors should nominate one author only to respond to such requests.
- CUP co-operates in various licensing schemes that allow material to be photocopied within agreed restraints (e.g., the CCC in the USA and the CLA in the UK). Any proceeds received from such licenses, together with any proceeds from sales of subsidiary rights in the Bulletin, directly support its continuing publication.
- It is understood that in some cases copyright will be held by the contributor's employer. If so, CUP (on behalf of AMPAI) requires exclusive permission to deal with requests from third parties, on the understanding that any requests received from third parties will be handled in accordance with paragraphs 4 and 5 above (note that approval will be sought for the proposed use from the contributor, not the employer).
- If a contribution includes textual or illustrative material not in your copyright and not covered by fair use/fair dealing, permission must be obtained from the relevant copyright owner (usually the publisher or via the publisher) for the nonexclusive right to reproduce the material worldwide in all forms and media, including electronic publication. The relevant permission correspondence must be attached to this form. If in doubt about whether or not permission is required, please consult: the Permissions Controller, Cambridge University Press, The Edinburgh Building, Shaftesbury Road, Cambridge CB2 2RU, UK. Fax: +44 (0)1223 315052. Email: lnicol@cambridge.org.
- The information provided on this form will be held in perpetuity by AMPAI for record purposes. The name(s) and address(es) of the author(s) of the contribution may be reproduced in the Bulletin and provided to print and online indexing and abstracting services and bibliographic databases