Indivisible partitions of latin squares

• Published in: Journal of statistical planning and inference 2011, Vol.141 (1), p.402-417
• Main Authors: Egan, Judith, Wanless, Ian M.
• Format: Article
• Language: English
• Subjects: Combinatorics; Combinatorics. Ordered structures; Designs and configurations; Exact sciences and technology; General topics; Indivisible partition; Latin square; Mathematics; Order, lattices, ordered algebraic structures; Parametric inference; Plex; Probability and statistics; Sciences and techniques of general use; Statistics; Transversal
• ISSN: 0378-3758; 1873-1171
• DOI: 10.1016/j.jspi.2010.06.020

In a latin square of order n, a k-plex is a selection of kn entries in which each row, column and symbol occurs k times. A 1-plex is also called a transversal. An indivisible k-plex is one that contains no c-plex for 0 < c < k . For orders n ∉ { 2 , 6 } , existence of latin squares with a partition into 1-plexes was famously shown in 1960 by Bose, Shrikhande and Parker. A main result of this paper is that, if k divides n and 1 < k < n then there exists a latin square of order n with a partition into indivisible k-plexes. Define κ ( n ) to be the largest integer k such that some latin square of order n contains an indivisible k-plex. We report on extensive computations of indivisible plexes and partitions in latin squares of order at most 9. We determine κ ( n ) exactly for n ≤ 8 and find that κ ( 9 ) ∈ { 6 , 7 } . Up to order 8 we count all indivisible partitions in each species. For each group table of order n ≤ 8 we report the number of indivisible plexes and indivisible partitions. For group tables of order 9 we give the number of indivisible plexes and identify which types of indivisible partitions occur. We will also report on computations which show that the latin squares of order 9 satisfy a conjecture that every latin square of order n has a set of ⌊ n / 2 ⌋ disjoint 2-plexes. By extending an argument used by Mann, we show that for all n ≥ 5 there is some k ∈ { 1 , 2 , 3 , 4 } for which there exists a latin square of order n that has k disjoint transversals and a disjoint ( n− k)-plex that contains no c-plex for any odd c.