Des. Codes Cryptogr. DOI 10.1007/s10623-009-9269-z Indivisible plexes in latin squares Darryn Bryant · Judith Egan · Barbara Maenhaut · Ian M. Wanless Received: 29 July 2008 / Revised: 9 January 2009 / Accepted: 12 January 2009 © Springer Science+Business Media, LLC 2009 Abstract A k-plex is a selection of kn entries of a latin square of order n in which each row, column and symbol is represented precisely k times. A transversal of a latin square corresponds to the case k = 1. A k-plex is said to be indivisible if it contains no c-plex for any 0 < c < k. We prove that if n = 2km for integers k ≥ 2 and m ≥ 1 then there exists a latin square of order n composed of 2m disjoint indivisible k-plexes. Also, for positive integers k and n satisfying n = 3k, n = 4k or n ≥ 5k, we construct a latin square of order n containing an indivisible k-plex. Keywords Latin square · Transversal · Plex · Orthogonal partition Mathematics Subject Classifications (2000) 05B15 · 62K99 1 Introduction A latin square of order n is an n × n matrix in which n distinct symbols are arranged so that each symbol occurs once in each row and column. Equivalently, a latin square may be defined as a set of n 2 elements, called entries, each of which is an ordered triple (x, y, z) such Communicated by L. Teirlinck. D. Bryant · B. Maenhaut Department of Mathematics, University of Queensland, QLD 4072, Australia e-mail: db@maths.uq.edu.au B. Maenhaut e-mail: bmm@maths.uq.edu.au J. Egan (B) · I. M. Wanless School of Mathematical Sciences, Monash University, VIC 3800, Australia e-mail: judith.egan@sci.monash.edu.au I. M. Wanless e-mail: ian.wanless@sci.monash.edu.au 123 D. Bryant et al. that symbol z appears at the intersection of row x and column y. We shall use the notation of the second definition. In a latin square L of order n, a k-plex is a subset of L consisting of kn entries in which each row, column and symbol is represented exactly k times. We call such a k-plex a k-plex of order n. A transversal of a latin square corresponds to the case k = 1. We call a k-plex an odd plex or an even plex if k is odd or even, respectively. Various names for specific cases of k-plexes have been used. Statistical literature sometimes refers to a transversal as a directrix and uses the terms duplex, triplex and quadruplex for a 2-, 3- and 4-plex, respectively. Other names are mentioned in [7]. We call a set of plexes parallel if no two of them share a common element. The union of an a-plex and a parallel b-plex in a latin square L yields an (a + b)-plex of L. The reverse process, that is dividing an (a + b)-plex into an a-plex parallel to a b-plex, is not necessarily possible. If a k-plex K contains no c-plex for 0 < c < k then it is said that K is indivisible. The existence of indivisible k-plexes for arbitrarily large k was first shown in [7]. It is obvious that a latin square L of order n is an n-plex. If L has a k-plex K , then the complement of K , that is L\K , is an (n − k)-plex. If L is partitioned into parallel plexes K 1 , K 2 , . . . , K m where each K i is a ki -plex, then K 1 , K 2 , . . . , K m is called a (k1 , k2 , . . . , km )-partition of L. In the case where each K i is a k-plex, we call the (k, k, . . . , k)partition a k-partition. If each plex in a partition is indivisible, then we say that the partition itself is indivisible. Interest in partitions of latin squares originally arose from applications in statistical experiments. There are several unsolved conjectures which deal with the existence of plexes. For example, Ryser’s conjecture states that every latin square of odd order has a transversal and Rodney’s conjecture states that every latin square has a 2-plex. These two conjectures are special cases of a conjecture from [7] that every latin square has the maximum possible number of parallel 2-plexes. Such conjectures and the evidence from small order examples [5] suggest that all latin squares are ‘highly divisible’ in the sense that they possess many different partitions. However, our first main result identifies, for the first time, a family of latin squares that have indivisible partitions with only two parts. Theorem 1.1 For every k ≥ 2 there exists a latin square of order 2k which contains two parallel indivisible k-plexes. Theorem 1.1 will follow immediately from Lemmas 3.2, 3.3 and 3.5. In Sect. 4 we investigate embedding the plexes from Theorem 1.1 in latin squares of larger orders. In doing so, we prove the following theorem which has Theorem 1.1 as a special case. Theorem 1.2 For integers k ≥ 2 and m ≥ 1 there exists a latin square of order 2km with an indivisible k-partition. Also in Sect. 4, we show that for positive integers k and n satisfying n = 3k, n = 4k or n ≥ 5k, any k-plex of order 2k is contained in a k-plex of order n. Application of Theorem 1.1 then shows that there exist indivisible k-plexes of every order n ≥ 5k. A question raised in [4] asks how large k can be if there exists an indivisible k-plex of order n. For any given n, let κ(n) be the largest k such that there exists a latin square of order n containing an indivisible k-plex. Previously, it was known [4] that if n is even, then κ(n) ≥ ⌊ 41 n⌋. A lower bound on κ(n) for odd n had not previously been shown, although, as explained later in this section, a closely related result was proved in [7]. Our third main result gives an improved bound for κ(n). 123 Indivisible plexes in latin squares Theorem 1.3 Let κ(n) be the largest integer k such that a latin square of order n contains an indivisible k-plex.
 κ(n) ≥ max np , ⌊ n5 ⌋ where p is the smallest prime divisor of n. There are several related problems that deal with partitions of various combinatorial designs. For example, Colbourn and Rosa ([2], p. 419) pose the analogue for Steiner triple systems of finding κ(n). Some other examples are discussed in [4]. A partial latin square (PLS) of order n is a subset P of R × C × S, where each of R, C and S is a set of cardinality n, such that no two distinct elements of P agree in more than one coordinate. The elements of P are called the entries of the PLS, and the elements of R, C and S are the rows, columns and symbols respectively. Often R = C = S and we then refer to this set as the index set of P, and denote it by I (P). A PLS P of order n with |P| = n 2 is a latin square. A PLS of order n is completable if it is a subset of some latin square of order n. We observe that although a k-plex of order n is a PLS of order n with kn entries and with the property that each row, column and symbol is represented k times, not every such PLS is a k-plex. Example (1) is a PLS of order 5 with 10 entries such that each row, column and symbol is represented twice. However, by inspection it is not completable and is therefore not a 2-plex by our definition. ⎞ ⎛ 0 1 · · · ⎜1 0 · · · ⎟ ⎟ ⎜ ⎜· · 2 3 · ⎟ (1) ⎟ ⎜ ⎝· · · 4 2⎠ · · 4 · 3 We call such PLSs, which may or may not be completable, protoplexes and we define them formally as follows. A k-protoplex of order n is a PLS of order n in which each row, column and symbol occurs exactly k times. Thus, a k-plex is a completable k-protoplex and vice versa. Although the concept is much older, the name plex was first used in [7]. The definition of k-plex used in this paper follows [4] and is a restriction of the original one. In defining a k-plex as a PLS Wanless [7] allowed that a k-plex be not necessarily completable; that is, a k-protoplex. Our definition of a protoplex is very similar to that of a homogeneous PLS, which is established terminology in the literature on latin trades [1]. However, unlike protoplexes, homogeneous PLSs are allowed to have empty rows and columns. As mentioned earlier, for odd n no lower bound on κ(n) was previously known. However in [7] it was shown that for arbitrary k and n ≥ k 2 there exists an indivisible k-protoplex of order n. This paper extends recent work by two of the authors [4]; indeed we rely on the infinite families of latin squares identified there. The papers [4] and [7] provide a more detailed survey of k-plexes in latin squares than given here. 2 Definitions and notation This section provides definitions and notation necessary for the proof of Theorem 1.1. Theorem 1.1 concerns latin squares of even order n = 2h. We use the index set Zn = E ∪ D where E = {0, 2, 4, . . . , n − 2} and D = {1, 3, 5, . . . , n − 1}, and we use the notation 123 D. Bryant et al. L[x, y] = z to define L. For example Z n [x, y] = (x + y) mod n defines the Cayley table of Zn . Definition 2.1 (Latin square Pn ) For n = 4q = 2h define ⎧ ⎨ (x + y + 2) mod n if x = n − 3 and y ∈ D, Pn [x, y] = (x + y − 2) mod n if x = n − 1 and y ∈ D, ⎩ (x + y) mod n otherwise. (2) Definition 2.2 (Latin square Qn ) For n = 2h where h ≥ 3 is odd, define ⎧ n−1 if x = y = 0 or x = y = n − 1, ⎪ ⎪ ⎪ ⎪ if {x, y} = {0, n − 1}, ⎨0 Qn [x, y] = (x + y − 2) mod n if x = 1 and y ∈ D, ⎪ ⎪ (x + y + 2) mod n if x = n − 1 and y ∈ D\{n − 1}, ⎪ ⎪ ⎩ (x + y) mod n otherwise. (3) Definition 2.3 (Latin square Rn ) For n = 4q = 2h define ⎧ ⎨ (x + y − 4) mod n if x = 3 and y ∈ D, Rn [x, y] = (x + y + 4) mod n if x = n − 1 and y ∈ D, ⎩ (x + y) mod n otherwise. (4) The latin square Q14 appears in Example 2.4. The latin square R4 given by (4) is equal to Z 4 . The notation which we describe in the remaining part of this section relies on context to make clear which latin square L of order n we are considering. Define r x to be the set of elements in row x of L. That is; r x = {(x, y, z) ∈ L | y, z ∈ Zn } . Also any subset X ⊆ L may be specified by simply indicating the columns represented in X for each row of L. If X is clear from context we define c(x) = {y | (x, y, z) ∈ r x ∩ X for some z ∈ Zn }. Let K be a k-plex in L and let X ⊆ L. Define X K = |X ∩ K |. The function : L → Zn is given by (e) = (z − x − y) mod n for each e = (x, y, z) ∈ L . Define ∗ ⊆ L and a ⊆ L by ∗ = {e ∈ L | (e) = 0}, a = {e ∈ L | (e) = a}. In the case when L = Pn it is immediate from (2) that; ∗ = −2 ∪ 2 where, 2 = {(x, y, z) ∈ rn−3 | y ∈ D}, −2 = {(x, y, z) ∈ rn−1 | y ∈ D}. 123 Indivisible plexes in latin squares Similarly, when L = Qn ; ∗ = −2 ∪ 2 ∪ I where I = −1 ∪ 1 , −2 = {(x, y, z) ∈ r1 | y ∈ D} , 2 = {(x, y, z) ∈ rn−1 | y ∈ D\{n − 1}}, (5) −1 = {( 0, 0, n − 1)} , 1 = {( 0, n − 1, 0 ), (n − 1, 0, 0 ), (n − 1, n − 1, n − 1)} . When L = Rn ; If n = 4, ∗ = ∅. Otherwise, ∗ = −4 ∪ 4 where, −4 = {(x, y, z) ∈ r3 | y ∈ D}, 4 = {(x, y, z) ∈ rn−1 | y ∈ D}. Example 2.4 Whenever we write one of the latin squares Pn , Qn or Rn we adopt the following convention. We write the rows and columns in the order 0, 2, 4, . . . , n −2, 1, 3, 5, . . . , n −1, as shown by our illustration of Q14 labelled (6) below. The reason for this will become clear in the next section when we prove Theorem 1.1. Entries with subscript ∗ are elements of ∗ and circled entries are elements of I . Shaded H = 0,  H = 3 and I H = 1. cells identify a 7-plex, which we name H . Observe that −2 2 1 3 5 7 9 0 2 4 6 8 10 12 13❧ ∗2 2 4 4 6 6 8 8 10 10 12 12 0 0 2 4 6 8 10 12 4 6 8 10 12 0 2 6 8 10 12 0 2 4 8 10 12 0 2 4 6 10 12 0 2 4 6 8 12 0 2 4 6 8 10 1 3 5 7 9 11 13 9 11 0❧ ∗ 11 13 1 13 1 3 1 3 5 3 5 7 5 7 9 7 9 11 1 3 5 7 9 11 13 1 3 3 5 5 7 7 9 9 11 11 13 0❧ ∗1 5 7 9 11 13 1 3 7 9 11 13 1 3 5 9 11 13 1 3 5 7 11 13 1 3 5 7 9 13 1 3 5 7 9 11 0 ∗ 2 ∗ 4 ∗ 6∗ 4 6 8 10 6 8 10 12 8 10 12 0 10 12 0 2 12 0 2 4 2 ∗ 4 ∗ 6∗ 8∗ 3 5 7 9 11 13 1 5 7 9 11 13 1 3 7 9 11 13 1 3 5 8∗ 12 0 2 4 6 10∗ 11 13 10∗ 0 2 4 6 8 12∗ (6) 12∗ 2 4 6 8 10 13❧ ∗ The illustrated 7-plex H is defined by the columns c(x) in r x ∩ H as follows: E if x ∈ {1, 3, 5, 6, 10, 12}, D if x ∈ {7, 9, 11}, c(0) = D\{13} ∪ {10}, c(x) = c(2) = D\{1} ∪ {12}, 123 D. Bryant et al. c(4) = D\{3} ∪ {2}, c(8) = D\{11} ∪ {0}, c(13) = {4, 6, 8} ∪ {1, 3, 11, 13}. 3 Indivisible h-partitions In this section we prove Theorem 1.1 in three cases. In each case we identify an h-partition of an appropriate latin square defined in the previous section and then prove that each of its two parts is indivisible. Throughout, assume that h = 21 n where n is the order of the latin square in context; either Pn , Qn or Rn . Many other partitions of the latin squares Pn and Qn are detailed in [4]. Notable, though unnecessary to the proof of Theorem 1.1, is that Pn and Qn have no k-plex for any odd k < ⌊ 41 n⌋ but do have a k-plex for every other k ≤ 21 n [4]. We rely on the following lemma from [4]. Lemma  3.1 [4] Let K be a k-plex in a latin  square L of order n. If n is even and k is odd then e∈K (e) ≡ 21 n mod n. Otherwise e∈K (e) ≡ 0 mod n. Lemma 3.2 For all odd q, the latin square R4q has an indivisible h-partition. Proof It is easy to check that R4 has an indivisible 2-partition. For q > 1, define H ⊂ R4q by: c(x) = E if x < h, D otherwise. (7) Note that since q is odd, h ≡ 2 mod 4. We now show that H is indivisible. Since 4H = h H = 0, a j-plex J contained in H has j =  J =  J . If j is odd, then Lemma 3.1 and −4 ∗ 4 says that 4 j ≡ h mod 4q. However 4 j ≡ 0 mod 4 and h ≡ 2 mod 4, so we can conclude that j is not odd. On the other hand, if j is even then Lemma 3.1 says that 4 j ≡ 0 mod 4q and thus, since j = q, we have j ∈ {0, h}. Hence H is indivisible. The proof that H ′ = R4q \H is indivisible is similar. ⊔ ⊓ The previous lemma proves Theorem 1.1 when k ≡ 2 mod 4. The next lemma proves the k ≡ 0 mod 4 case. Lemma 3.3 For all even q, the latin square P4q has an indivisible h-partition. Proof Define H ⊂ P4q by: c(x) = E if (x ∈ E and x < h) or (x ∈ D and h − 1 ≤ x < n − 1), D otherwise. (8) H = h and  H = 0. We rely on Note that since q is even, h ≡ 0 mod 4. We have −2 2 Lemma 3.1 and follow the process of the proof of Lemma 3.2. ⊓ ⊔ As an aside to our proof of Theorem 1.1 note that (8) defines an h-partition of P4q regardless of the parity of q. If q is odd then both parts of the identified h-partition are examples of plexes which contain no even plex, but do, as is easily verified, contain q-plexes. On the other hand, a slightly different h-plex of P4q given by (9) below puts all of ∗ into one plex. The result is an h-partition in which both parts contain only even plexes. c(x) = 123 E if x < h, D otherwise. (9) Indivisible plexes in latin squares We do not know if P4q has an indivisible h-partition when q is odd, although we did find h-partitions in which one part is indivisible. We now return to the proof of Theorem 1.1. In the third and final case we rely on conditions other than Lemma 3.1. A latin square of order ms is said to be of s-step type if it can be represented by a matrix of s × s blocks Bi j as follows ⎞ ⎛ B11 B12 . . . B1m ⎜ B21 B22 . . . B2m ⎟ ⎟ ⎜ ⎜ .. .. . . . ⎟ ⎝ . . .. ⎠ . Bm1 Bm2 . . . Bmm where each block Bi j is a latin subsquare of order s and two blocks Bi j and Bi ′ j ′ contain the same symbols if and only if i + j ≡ i ′ + j ′ mod m. The structure of the latin square Qn of order n = 2h may be thought of as an h-step type latin square which has been corrupted by one element in each block. More specifically,   B00 B01 Qn = B10 B11 where each of B00 and B11 is an h × h latin subsquare based on the symbols of E except that each has precisely one occurrence of a symbol from D, and each of B01 and B10 is an h × h latin subsquare based on the symbols of D except that each has precisely one occurrence of a symbol from E. Thus, there are four corrupted entries in Qn . It is a classical observation (eg. see a theorem by Mann [3, p. 448]) that if there are c corrupted entries in one block of an h-step type latin square of order 2h, then there are c corrupted entries in each block of the square. We will call such a square a c-corrupted h-step type latin square. We now consider the number of elements in a k-plex found in the h × h blocks of a c-corrupted h-step type latin square. Lemma that L is a c-corrupted h-step type latin square of order n = 2h where  3.4 Suppose  B00 B01 L= and c entries of B00 have symbols from D, and the remaining h 2 −c entries B10 B11 of B00 have symbols from E. If K ⊆ L is a k-plex, then the following conditions are satisfied. K = B K , and B K = B K . 1. B00 11 01 10 K − B K ≤ 2c. 2. −2c ≤ B00 01 K − B K < 2c. 3. If both k and h are odd, then −2c < B00 01 Proof Each of the h rows of B00 ∪ B01 and each of the h columns of B01 ∪ B11 is repreK + B K = kh = B K + B K , hence B K = B K . Similarly sented k times in K . Therefore B00 01 01 11 00 11 K K B01 = B10 , thus part 1 of the Lemma is shown. Next we partition each Bi j into Ai j and Ci j such that for all e = (x, y, z) ∈ Bi j , e ∈ Ai j if (z ∈ D and i = j) or (z ∈ E and i = j), e ∈ Ci j otherwise. (10) K + AK + Consider part 2 of the Lemma. Each symbol in E is represented k times in K so A00 11 K K C01 + C10 = k|E| = kh. Hence, rearranging terms; 
K K K K A00 . (11) = kh − C01 + C10 + A11 123 D. Bryant et al. Similarly, counting symbols of D in K ;
 K K K K A01 + A10 = kh − C00 + C11 . (12) K − B K > 2c. Then B K − B K > 2c. Summing these two inequalities Now assume that B00 01 11 10 K and substituting Bi j = AiKj + CiKj gives
 
K K K K K K K K A00 > 4c. (13) − A01 + A10 + C01 + C10 + A11 + C00 + C11 K + C K − C K − C K > 2c, which is Substituting (11) and (12) into (13) we obtain that C00 11 01 10 K K K − B K < −2c a contradiction since C00 ≤ c and C11 ≤ c. It follows, by symmetry, that B00 01 must also be false. Thus part 2 of the Lemma has been shown.   K − B K = B K − kh − B K = 2B K − kh is odd, Now if k and h are both odd, then B00 01 00 00 00 so part 3 of the Lemma follows. ⊔ ⊓ Now we are ready to prove Theorem 1.1 in the case that k is odd. Lemma 3.5 For all odd h ≥ 3, the latin square Q2h has an indivisible h-partition. Proof First we identify an h-partition. A 7-partition of Q14 is shown in (6). For n = 2h = 14 we show an h-plex H by specifying the columns c(x) to use in r x ∩ H . c(0) = {n − 2} ∪ D\{n − 1}, (14) c(n − 1) = {y ∈ E | y ≡ 2 mod 4} ∪ {y ∈ D | y ≡ 1 mod 4}, (15) For x ∈ D\{n − 1}, c(x) = E if x < h, D if x ≥ h. For x ∈ E\{0} we specify c(x) in three cases, as follows. Case 1 h ≡ 1 mod 4 (h ≥ 5). ⎧ ⎨ {x − 4} ∪ D\{x − 3} if x ∈ E\{0}, x < h and x ≡ 0 mod 4, c(x) = {x − 2} ∪ D\{x − 1} if x ∈ E, x > h and x ≡ 2 mod 4, ⎩ E otherwise. Case 2 h ≡ 3 mod 8 (h ≥ 3). For h = 3, c(2) = {0, 4, 3}, c(4) = {0, 2, 5}. For h ≥ 11, c(h − 3) = {0} ∪ D\{1}, For a ∈ {0, 4, 8, . . . , 21 (h − 11)}, c(h − 7 − a) = {h − 3 − a} ∪ D\{h − 2 − a}, c(h − 5 − a) = {n − 6 − a} ∪ D\{n − 5 − a}, c(h + 1 + a) = {4 + a} ∪ D\{5 + a}, c(h + 3 + a) = {h + 1 + a} ∪ D\{h + 2 + a}. Otherwise, c(x) = E. 123 (16) Indivisible plexes in latin squares Case 3 h ≡ 7 mod 8 (h ≥ 15) For a ∈ {0, 4, 8, . . . , 21 (h − 7)}, c(h − 7 − a) = {h − 3 − a} ∪ D\{h − 2 − a}, c(h − 1 − a) = {n − 6 − a} ∪ D\{n − 5 − a}, c(h + 1 + a) = {a} ∪ D\{1 + a}, c(h + 3 + a) = {h + 1 + a} ∪ D\{h + 2 + a} if a ≤ 21 (h − 15). Otherwise, c(x) = E. This completes all cases for h mod 8. It is routine to check that H is an h-plex. We proceed by contradiction to show that H and H ′ = Q2h \H are indivisible.  With c = 1, consider the sets Ai j , Bi j and Ci j of Q2h as described in (10). By definition, i, j∈{0,1} Ci j = I where I is given by (5). Note that all cases of H , including that given separately in (6), obey (16) for their definition of H ∩ (B10 ∪ B11 )\rn−1 . Further, by (6), (14) and (15), we see that H ∩ I = C11 , H ∩ rn−1 ∩ B11 = H ∩ ∗ and H ∩ rn−1 ∩ A11 = H ∩ 2 . We rely on these facts in the following argument. Assume that H is divisible. Then H contains an odd k-plex K ⊂ H with k < h. It K ≥  K = 1 (h + 1). follows from Lemma 3.1 that K ∩ ∗ = H ∩ ∗ . Therefore k = rn−1 ∗ 2 Also I ∩ H = C11 ⊂ (K ∩ ∗ ), so if e ∈ K \C11 , then e ∈ Ai j for some i, j. Consider K ∩(A10 ∪ A11 )\rn−1 . Following from (16) there are 21 (h −1) rows r x such that H ∩r x ⊂ A10 and 21 (h − 1) rows r x such that H ∩ r x ⊂ A11 . Hence, K = (A11 \rn−1 ) K + ∗K ≥ 21 k(h − 1) + 21 (h + 1), B11 K B10 K K = (A10 \rn−1 ) + (rn−1 \∗ ) ≤ 1 2 k(h − 1) + 1 2 (h (17) − 1). (18) K − B K ≤ 1 so the inequalities in (17) and (18) must be equalities. Lemma 3.4 requires that B11 10 K K K = kh −k + h +1 using (17). Counting occurrences Also B00 = B11 so (B00 ∪ B11 ) K = 2B11 of the symbols, k|E| = (B00 ∪ B11 \C11 ) K implies that kh = kh − k + h. This contradicts k < h and thus shows that H is indivisible. Next we consider H ′ . In this case I ∩ H ′ = I \C11 . Following similar reasoning as for H we find that if K ⊂ H ′ is an odd k-plex, then (B10 \rn−1 ) K = (A10 \rn−1 ) K = 21 k(h − 1), and (B11 \rn−1 ) K = (A11 \rn−1 ) K = 21 k(h − 1). Hence by Lemma 3.4; (rn−1 ∩ B10 ) K − (rn−1 ∩ B11 ) K = ±1. (19) H′ We also note that rn−1 ∩ A11 ∩ H ′ = 2 ∩ H ′ , with 2 = 21 (h − 1) and that −2 = r1 ∩ H ′ H ′ = h. so −2  Let J = H ′ \K be a j-plex (with j > 0 even). By Lemma 3.1, e∈J ∩I (e) is even. Thus we consider two cases.  Case 1 e∈J ∩I (e) = 0. J . Also j =  J so it follows that (r J Lemma 3.1 requires that 2J = −2 n−1 ∩ B10 ) = −2 ′ 1 J K H j − 2 = 0. Then (rn−1 ∩ B10 ) = (rn−1 ∩ B10 ) = 2 (h + 1). However now (rn−1 ∩ ′ B10 ) K > (rn−1 ∩ B11 ) H so by (19), (rn−1 ∩ B11 ) K = 21 (h − 1) and j = 2J = 0, which is a contradiction.  Case 2 e∈J ∩I (e) = 2. 1 J =  J + 1 so j =  J + 1, and (r K Lemma 3.1 requires that −2 n−1 ∩ B10 ) = 2 (h − 1). 2 2 123 D. Bryant et al. Thus, the right hand side of (19) is positive, so 2K = 21 (h − 3) and we have k = h − 2 and J = AJ = j = 2. By the Case 2 assumption, C00 ⊂ K , and (C01 ∪ C10 ) ⊂ J , hence B11 11 1 J J J J J + (C ∪ J 2 + 2 j (h − 1) = h, so by Lemma 3.4, A00 = B00 = B11 = h. Thus A00 + A11 01 C10 ) J = 2h + 2. Since this is not equal to j|E| = j h, we have a contradiction. The contradictions in the two cases show that H ′ is indivisible. ⊔ ⊓ 4 Embedding plexes We begin this section by giving some preliminary lemmas on combining (proto)plexes into larger ones. These are used to prove Theorems 1.2 and 1.3. In contrast to Sects. 2 and 3, we are now interested in latin squares of any order, even or odd. Let P and P ′ be partial latin squares with pairwise disjoint index sets I (P) and I (P ′ ). We define the direct sum P ⊕ P ′ to be the PLS P ∪ P ′ with index set I (P) ∪ I (P ′ ). We define the product P ⊗ P ′ to be the PLS    P ⊗ P ′ = (x, x ′ ), (y, y ′ ), (z, z ′ ) | (x, y, z) ∈ P and (x ′ , y ′ , z ′ ) ∈ P ′ . with index set I (P) × I (P ′ ). The next two results follow immediately from these definitions. Lemma 4.1 If K = K 1 ⊕ K 2 ⊕ · · · ⊕ K s then K contains a c-protoplex if and only if K i contains a c-protoplex for each i ∈ {1, 2, . . . , s}. Lemma 4.2 If K is an a-plex of order n and K ′ is a b-plex of order n ′ , then K ⊗ K ′ is an ab-plex of order nn ′ . Furthermore, if K 1 , K 2 , . . . , K s is a partition of a latin square L and K 1′ , K 2′ , . . . , K t′ is a partition of a latin square L ′ , then {K i ⊗ K ′j | i = 1, 2, . . . , s, j = 1, 2, . . . , t} is a partition of L ⊗ L ′ . An immediate consequence of Lemma 4.2 is that if K 1 , K 2 , . . . , K s is a k-partition of L and K 1′ , K 2′ , . . . , K t′ is a k ′ -partition of L ′ , then L ⊗ L ′ has a kk ′ -partition. Lemma 4.3 Let K 0 and K 1 be parallel k-plexes in a latin square of order 2k. Then there is a k-partition of a latin square of order 4k all parts of which are isotopic to K 0 ⊕ K 1 . Proof We define a latin square of order 4k with index set I (K 0 ) ∪ {i ′ | i ∈ I (K 0 )} and k-partition {P1 , P2 , P3 , P4 } where   P1 = K 0 ∪ (x ′ , y ′ , z ′ ) | (x, y, z) ∈ K 1 ,     P2 = (x ′ , y, z ′ ) | (x, y, z) ∈ K 0 ∪ (x, y ′ , z) | (x, y, z) ∈ K 1 ,     P3 = (x, y ′ , z ′ ) | (x, y, z) ∈ K 0 ∪ (x ′ , y, z) | (x, y, z) ∈ K 1 ,     P4 = (x ′ , y ′ , z) | (x, y, z) ∈ K 0 ∪ (x, y, z ′ ) | (x, y, z) ∈ K 1 . It is clear that each Pi is isotopic to K 0 ⊕ K 1 . ⊔ ⊓ We can now prove Theorem 1.2 which states that for integers k ≥ 2 and m ≥ 1 there exists a latin square of order 2km with an indivisible k-partition. Proof (of Theorem 1.2) Let L be the latin square of order 2k with an indivisible k-partition guaranteed by Theorem 1.1. For m ∈ {2, 6}, we apply Lemma 4.2 to L and L ′ where L ′ is a latin square of order m possessing a 1-partition. For m = 2 we apply Lemma 4.3 to L. For m = 6 we apply Lemma 4.2 to L and a latin square of order 3, followed by Lemma 4.3. In all cases, Lemma 4.1 guarantees that the resulting k-partition is indivisible. ⊔ ⊓ 123 Indivisible plexes in latin squares We will soon construct latin squares of various additional orders which contain k-plexes that are direct sums of two k-protoplexes. By taking one of these to be a k-protoplex from Theorem 1.1, the resulting k-plexes will be indivisible. First we prove restrictions on the order of a latin square that contains a k-plex that is a direct sum of two k-protoplexes. Lemma 4.4 If K = K 0 ⊕ K 1 is a k-plex, where K 0 is a k-protoplex of order m and K 1 is a k-protoplex of order n − m, then n 2 − (3m + k)n + 3m 2 ≥ 0. Proof Let L be the latin square containing K and define X = {(x, y, z) ∈ L | x ∈ I (K 0 ), y ∈ I (K 1 )} . Consider the m symbols of I (K 0 ). The number of occurrences of each of these in the rows indexed by I (K 0 ) is m, and the number of occurrences in K 0 is k. Hence the number of occurrences of each of these symbols in X is at most m −k. Similarly, the number of occurrences of each of the n −m symbols of I (K 1 ) in X is at most n −m −k. Since the total number of occurrences of symbols in X is m(n−m), it follows that m(n−m) ≤ m(m−k)+(n−m)(n−m−k). Rearranging, we obtain the required inequality. ⊔ ⊓ Putting m = 2k in Lemma 4.4 we obtain (n − 3k)(n − 4k) ≥ 0 and thus n ≤ 3k or n ≥ 4k. However, n < 3k implies that K 1 is k-protoplex of order less than k, which is impossible. Thus, we have the following corollary which tells us the orders of latin squares in which it may be possible to embed our indivisible k-protoplexes of order 2k. Corollary 4.5 If K = K 0 ⊕ K 1 is a k-plex, where K 0 is a k-protoplex of order 2k and K 1 is a k-protoplex of order n − 2k, then either n = 3k or n ≥ 4k. In what follows, we will show that there exists a latin square of order n with an indivisible k-plex for all n allowed (given that our k-plex is a direct sum involving a k-protoplex of order 2k) by Corollary 4.5, except for n in the range 4k < n < 5k. Lemma 4.6 A k-protoplex K of order m ≥ 2k can be extended to a k-plex of order 2m − k that is a direct sum involving K . Proof The result is trivial in the case m = 3 and k = 1 so assume otherwise. Let K 0 be a k-protoplex of order m and let L 1 be a latin square of order m − k containing a k-plex K 1 . Since m ≥ 2k (and (m, k) = (3, 1)), L 1 exists (see [7]). We now show that K 0 ⊕ L 1 is completable, thus showing that K 0 ⊕ K 1 is the required k-plex. To complete K 0 ⊕ L 1 we need to (1) fill the rectangle R01 = {(x, y) | x ∈ I (K 0 ), y ∈ I (K 1 )}, (2) fill the rectangle R10 = {(x, y) | x ∈ I (K 1 ), y ∈ I (K 0 )}, and (3) fill the unfilled cells with row and column indices in I (K 0 ). Each of (1–3) may be done independently, and each is equivalent to finding a 1-factorisation of an (m − k)-regular bipartite graph with m vertices in each part. The existence of such factorisations is well known, and is an easy consequence of Hall’s Marriage Theorem [6]. ⊓ ⊔ The dark shaded entries in the following latin square show the indivisible 3-plex of order 6 (from Q6 and Lemma 3.5), extended to an indivisible 3-plex of order 9. The lighter shaded entries in the square identify a parallel 3-plex. A computer search shows that the resultant 123 D. Bryant et al. 3-partition is indivisible. ⎛ 6 2 4 1 8 7 7 8 0 3 6 1 4 0 6 5 7 8 1 6 8 7 4 2 3 5 7 8 0 6 8 7 3 6 2 5 ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ 5 2 3 0 4 1 ⎜ ⎝ 3 4 2 5 1 0 0 5 1 3 2 4 5 4 2 0 1 3 2 3 1 4 5 0 0 1 5 2 3 4 ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ 6 7 8 ⎟ ⎟ 7 8 6 ⎠ 8 6 7 Lemma 4.7 Let m ≥ k ≥ 1 and n ≥ 2m + k. For any k-plex K of order m there exists a k-plex K ⊕ K ′ of order n. Proof Let L be a latin square of order m containing a k-plex K . Let S be a set of n − m symbols distinct from I (L) and let γ be a permutation applying a single n − m cycle to S. By [8] there exists a latin square L ′ ⊃ L of order n, indexed by I (L) ∪ S and such that L ′ has an automorphism α that applies γ simultaneously to the row, column and symbol indices. We obtain the required k-plex by taking the union of K with k orbits of α on entries whose row, column and symbol indices are in S. The condition n ≥ 2m + k ensures that |S| − m ≥ k, so there are enough suitable orbits for this construction. ⊔ ⊓ Note that applying Lemma 4.6 or Lemma 4.7 to the indivisible k-plex of order 2k from Theorem 1.1, we obtain an indivisible k-plex of order n for n = 3k and all n ≥ 5k, respectively. Also, applying Theorem 1.2 with m = 2 gives us, for each k ≥ 2, a latin square of order 4k with an indivisible k-plex. We state these facts in the following corollary. Corollary 4.8 For all k ≥ 2, there exists an indivisible k-plex of order n for n = 3k, n = 4k and all n ≥ 5k.
 We are now ready to prove Theorem 1.3 which states that κ(n) ≥ max np , ⌊ n5 ⌋ where p is the smallest prime divisor of n. Proof (of Theorem 1.3) Let p be the smallest prime divisor of n. If p = 2 or p = 3, then the existence of a latin square of order n with an indivisible ( np )-plex is guaranteed by Theorem 1.1 or the n = 3k result in Corollary 4.8, respectively. If p ≥ 5, then the existence of a latin square of order n with an indivisible ⌊ n5 ⌋-plex follows from the n ≥ 5k result in Corollary 4.8. ⊔ ⊓ The results of this section leave open the following question: for 4k < n < 5k can a k-protoplex of order 2k always be extended to a k-plex of order n? There do exist some results that are related to this question. A theorem in [7] states that if 1 < k < n and k > 41 n, then there exists an uncompletable k-protoplex of order n. Several people have conjectured (see [7]) that for k ≤ 41 n every k-protoplex of order n is a k-plex of order n. It would also be particularly interesting to know the asymptotic behaviour of κ(n). In [5] it is found that κ(n) > 21 n at least for 5 ≤ n ≤ 9, so there may be room to improve Theorem 1.3. An extension to Theorem 1.2 is shown in [5]. 123 Indivisible plexes in latin squares References 1. Cavenagh N.J., Donovan D.M., Yazici E.S.: Minimal homogeneous latin trades. Discrete Math. 306, 2047–2055 (2006). 2. Colbourn C.J., Rosa A.: Triple Systems. Clarendon Press, Oxford (1999). 3. Dénes J., Keedwell A.D.: Latin squares and their applications. Akadémiai Kiadó, Budapest (1974). 4. Egan J., Wanless I.M.: Latin squares with no small odd plexes. J. Comb. Des. 16, 477–492 (2008). 5. Egan J., Wanless I.M.: Indivisible partitions of latin squares (preprint). 6. Hall P.: On representatives of subsets. J. London Math. Soc. 10, 26–30 (1935). 7. Wanless I.M.: A generalisation of transversals for latin squares. Electron. J. Comb. 9, R12 (2002). 8. Wanless I.M.: Diagonally cyclic latin squares. Eur. J. Comb. 25, 393–413 (2004). 123