PAGE 1
THERE IS NO TWOTHREE SUBSQUARE COMPLETE LATIN SQUARE OF ORDER ELEVEN by Jim Calhoun A., University of Denver, 1974 A thesis submitted to the University of Colorado at Denver in partial fulfillment of the requirements for the degree of Masters of Science Applied Mathematics 1996
PAGE 2
This thesis for the Masters of Science degree by Calhoun has been approved by tan Payne
PAGE 3
Calhoun, Jim (M. S., Applied Mathematics) There is no TwoThree Subsquare Complete Latin Square of Order Eleven Thesis directed by Professor William Cherowitzo ABSTRACT A latin square of order n is an n x n array containing n elements, each element appearing exactly once in each row and column. A latin square, A, of order n is said to contain a proper subsquare, B, of order m, 1 < m < there exists an intersection of m rows and columns within A that is also a latin square. every pair of identical elements in latin square A is contained in a proper subsquare then the latin square A is called subsquare complete (sq. all the sub squares in a SC latin square are of order 2 or 3, then it is called 23SC. has been shown that, up to isotopy there exists unique 23SC latin squares of order 4, 6, 7, 8, 9, and 10, three of order 12, and none of order S. None been found of order 11. In this paper we prove that there does not exist a 23SC latin square of order 11. This abstract accurately represents the content of the candidate's thesis. I recommend its publication:
PAGE 4
CONTENTS Chapter 1. Definitions................................................... .............. 1. 2. Current Results ............................................................. 4 3. LSII. .................................................................... 10 3.1 Configuration of Two Rows in LS 11 ......................................... 10 3.2 A Third Row in LSI!. ................................................... 11 3.3 Building Four Rows of LSI!. ............................................. 18 3.4 NonExistence of LSI 1. ................................................... 22 4. Higher Orders of SC Latin Squares .............................................. 27 Bibliography .................................................................. 29 iv
PAGE 5
1. Definitions latin square, of order n, is an n x n array containing n distinct elements each of which occurs exactly once in each row and column of the array. latin subsquare, B, of order m consists of the intersection of m rows and columns of which is itself a latin square. The rows and columns ofB do not have to be contiguous. 1 < m < n then B is called a proper subsquare of Figure 1.1 shows a latin square of order 7 with the underlined elements forming a proper subsquare of order 3. Figure 1.2 is a latin square of order 6 with a proper subsquare of order 3 in each 3 x 3 comer. 2 3 5 2 3 4 5 1 7 3 4 2 7 1 5 5 3 2 5 1 7 3 4 2 7 1 2 5 3 5 2 3 Figure 1.1 1 3 5 3 1 4 5 3 1 2 5 4 4 5 6 1 2 3 5 2 3 1 6 4 5 3 1 2 Figure 1.2
PAGE 6
Hiner [3] defined a latin square A, to (SC) every pair of identical elements in A is in a proper subsquare of A. an ... all the proper subsquares of A have order a., p, ... or y. this paper we are interested in 23SC latin squares. Figure 1.3 shows a 23SC latin square of order 6. Notice that the latin squares in Figures and 1.2 are not 23SC. 2 3 4 5 6 2 3 6 4 5 3 2 5 6 4 4 5 6 2 3 5 6 4 3 2 6 4 5 2 3 Figure 1.3 Another way to view a latin square is as the multiplication table of a quasigroup. A is a S, closed under a binary operation such that given any a and b E S, ax=b and ya=b have unique solutions for x and y. Two quasigroups, (G,) and (H,EB), are isotopic there is an ordered triple, (9, of bijections from G to H such that 9(x) EB = 'V(xy) for all x and y E G. The bijection 'V operates on the elements ofG, while 9 and, operate on the rows and columns of the table of G. In a latin square this equates to three operations: 1) permuting the rows 2) permuting the columns 3) permuting the elements one latin square can changed to another by means of any or all of these operations then the two squares are called A T, ofa latin square A is a set ofn cells, one from each row and column that contain n distinct elements. An example of a latin square with a transversal is given in Figure 1.4. The elements in the transversal are underlined. 2
PAGE 7
! 2 3 4 5 6 2 4 6 5 3 6 4 4 5 2 3 5 3 2 6 6 4 3 2 Figure l.4 A latin square A of order n with a transversal, T, can be used to create a latin square of order n + l. To do this, start with A and add row n+ 1 and column n+ 1. For each element, aij E T, insert aij into cells (i,n+1) and (n+1j). Put new element n+ 1 the cells ofT and also in cell (n+1, n+1). Figure l.5 is a latin square of order 7 created from the latin square of order 6 with the transversal of Figure l.4. This process is called 7 2 3 4 5 6 2 4 7 5 3 3 7 4 2 4 7 5 2 3 5 3 2 7 4 6 4 7 3 2 6 5 2 3 4 7 Figure l.5 is the reverse process. Specific orders of23SC latin squares obtained by prolongation and antiprolongation will be described in the next section. 3
PAGE 8
2. Current Results Hiner and Killgrove found all 23SC latin squares of orders less eleven and partially published the results [3). A more complete listing of the results was given by Killgrove and Milne [5). For each of the orders 4,6, 7, 8, 9, and 10 there is exactly one 23SC latin square (up to isotopy). There is none of order 5. Killgrove and Milne have shown that there are exactly three 23SC latin squares of order 12. They researched these because of their relation to projective planes not generated by a quadrangle. They skipped latin squares of order eleven since these would not lead to planes. this paper we prove that there is no 23SC latin square of order eleven. The 23SC latin squares of order 4 and 8 are the 2SC latin squares that come from the addition tables of the abelian groups of order 22 and 23. These are shown in Figures 2.1 and 2.2 respectively. 1 2 3 4 2 1 4 3 3 4 1 2 4 3 2 1 Figure 2.1 1 2 3 4 5 6 7 8 2 1 4 3 6 5 8 7 3 4 1 2 7 8 5 6 4 3 2 8 7 6 5 5 6 7 8 1 2 3 4 6 5 8 7 2 1 4 3 7 8 5 6 3 4 2 8 7 6 5 4 3 2 Figure 2.2 4
PAGE 9
Hiner and Killgrove have shown that the table of any elementary abelian group of order 2B is a 2SC latin square. Heinrich and Wallis also proved this [2]. The 23SC latin square of order six in Figure l.3 is the table for the non cyclic symmetric group S3. Hiner and Killgrove showed that the table of a noncyclic group is SC. The orders of the subsquares are the orders of the elements of the group. This method results in one of the SC latin squares of order twelve, shown in Figure 2.3. This is the table of the alternating group 1 2 3 4 5 6 7 8 9 10 11 12 2 3 1 6 4 5 8 9 7 12 10 11 3 1 2 5 6 4 9 7 8 11 12 10 4 7 10 1 8 2 5 12 3 6 9 5 9 3 7 12 1 6 10 2 4 8 6 8 12 2 9 10 3 4 1 5 7 7 10 4 1 8 5 12 2 9 3 6 8 12 6 10 2 9 4 3 7 1 5 9 11 5 12 3 7 6 10 1 8 2 4 10 4 7 8 11 1 12 2 5 6 9 3 11 5 9 7 12 3 10 1 6 4 8 2 12 6 8 9 10 2 3 4 5 7 1 Figure 2.3 Hiner and Killgrove constructed another 23SC latin square of order twelve. is shown in Figure 2.4. 5
PAGE 10
1 2 3 4 5 6 7 8 9 10 11 12 2 3 1 5 6 4 8 9 7 11 12 10 3 1 2 6 4 5 9 7 8 12 10 11 4 6 5 1 3 2 12 11 10 9 8 7 5 4 6 2 1 3 11 10 12 8 7 9 6 5 4 3 2 1 10 12 11 7 9 8 7 9 8 12 11 10 1 3 2 6 5 4 8 7 9 11 10 12 2 1 3 5 4 6 9 8 7 10 12 11 3 2 1 4 6 5 10 12 11 9 8 7 6 5 4 1 3 2 11 10 12 8 7 9 5 4 6 2 1 3 12 11 10 7 9 8 4 6 5 3 2 1 Figure 2.4 KiUgrove and Milne constructed the third 23SC latin square of order twelve by hand and by computer [5J. It is shown in Figure 2.5. 6
PAGE 11
1 2 3 4 5 6 7 8 9 10 11 12 2' 3 1 5 6 4 8 9 11 12 10 3 1 2 7 8 9 10 11 12 4 5 6 4 5 6 11 12 10 9 7 8 3 1 2 5 7 12 8 1 11 2 4 10 9 6 3 6 12 9 10 2 8 4 1 11 7 3 5 7 4 10 9 11 3 12 5 2 6 8 1 8 9 7 2 3 1 5 6 4 12 10 11 9 11 4 3 10 7 6 12 1 5 2 8 10 6 8 12 9 2 3 5 1 7 4 8 5 1 7 12 3 10 6 2 4 9 12 10 11 6 4 5 1 2 3 8 9 7 Figure 2.5 The 23SC latin square of order nine is a 3SC latin square. is the table of the elementaIy abelian group of order 9. This is shown in Figure 2.6. KiUgrove [4] showed that the table ofan elementaIy abelian group of order n 3is a 3SC latin square. 1 2 3 4 5 6 7 8 9 2 3 1 5 6 4 8 9 7 3 1 2 6 4 5 9 7 8 4 5 6 7 8 9 1 2 3 5 6 4 8 7 2 3 1 6 4 5 9 7 8 3 1 2 7 8 9 2 3 4 5 6 8 9 7 2 3 5 6 4 9 7 8 3 2 6 4 5 Figure 2.6 7
PAGE 12
Hiner and Killgrove proved that 23SC latin squares of order 211 1 be constructed by antiprolongation from the table of the elementaI)' abelian group of order 2". Figure 2.7 shows one of order 7 constructed from the order 8 23SC latin square shown in Figure 2.2. 8 2 3 4 6 7 2 7 4 3 6 5 8 3 4 6 2 7 8 4 3 2 8 7 6 5 6 7 8 4 2 3 6 5 8 7 2 3 4 7 8 6 3 4 2 Figure 2.7 They also showed that 23SC latin squares of order 3 1 be constructed by prolongation from the table of an elementary abelian group of order 3 One of order ten is shown in Figure 2.8. is constructed from the 23SC latin square of order 9 in Figure 2.6. A proof of these two constructions can be found Heinrich [1]. 8
PAGE 13
10 2 3 4 6 7 8 9 1 2 10 1 6 4 8 9 7 3 3 1 10 6 4 9 7 8 2 4 6 10 8 9 1 2 3 7 6 4 8 10 7 2 3 1 9 6 4 9 7 10 3 1 2 8 7 8 9 1 2 3 10 6 4 8 9 7 2 3 1 10 4 6 9 7 8 3 1 2 6 4 10 1 3 2 7 9 8 4 6 10 Figure 2.8 9
PAGE 14
3. LSll I speculated that a 23SC latin square of order eleven existed and set out to find one. Using the logic of the Fortran program Killgrove and Milne used in [5] I wrote a computer program, but was surprised when it came up empty. Bill Cherowitzo wrote a program to verify my result. The proof in this paper is a result of my research to discover why one does not exist. The method to show nonexistence is contradiction. We will asswne that a 23SC latin square of order 11 exists. We will call it LS 11. We will determine some of its properties for the purpose of building it. Then, when we to build it, we will see that it does not exist. 3.1 Configurations of Two Rows in LSll We will call a subsquare of order two a and a subsquare of order three a Two rows of a triad is a We will now look at the possible configurations of two rows. In a 23SC latin square of order 11 we define the set Cl as the set of unordered pairs of rows having four duads and one partialtriad. We define the set C2 as the set of unordered pairs ofrows with one duad and three partialtriads. Lemma 3.1.1 Let LS 11 be a 23SC latin square of order 11. Every pair of distinct rows in LS 11 must be in Cl or C2. Proof: Let ra and rb be two distinct rows in LS 11, a 23SC latin square. Every element in ra must be in a duad or triad with its matching element in rb. AIl the elements cannot be in duads since there are an odd number of elements. So there must exist at least one partialtriad in ra and rb. There are 8 elements not in this partialtriad, which may be contained in 4 duads. In this case, {raJ rb} e C1. There can't be two partialtriads because that would leave 5 elements, which cannot evenly put into duads. Three partialtriads are possible, requiring 9 elements, which leaves exactly 2 elements to be in one duad. In this case {r a rb} e C2. 10
PAGE 15
Ifwe take r. and rb out of LSll and set them up in a 2 by 11 latin rectangle, LRIo then LRI must be isotopic to one of the following two 2 by 11 latin rectangles. Figure 3.1.1 {ra, rb} E C1. In Figure 3.1.2 {ra, rb} C2. 2 3 4 5 6 7 8 10 2 3 5 4 7 9 8 11 10 Figure 3.1.1 2 3 4 6 7 8 9 10 11 2 3 8 9 7 11 10 Figure 3.1.2 Theorem 3.1.1 LSll must have two rows that are in C2. Proof: Assume that given any two rows, ra and rb, in LSll, {r., rb} C1. Then all row pairs contain four duads and one partialtriad. The number ofrow pairs is = (11 10) /2 = 55. Each triad in LSll requires rows and (3*2)/2 3 sets ofrow pairs. If {r a rb} E Cl, then ra and rb contain one partialtriad. There must be another row, call it r e to complete the triad. These three rows, taken in pairs, are in 3 row pairs, {ra rb}, {ra re} and {rb, re}. Likewise every triad requires three distinct sets of row pairs. But we have 55 row pairs and since 3 does not divide 55 we must have an incomplete triad, and so, LSII can't be 23SC. Therefore in LSII there must be at least one row pair that is in the set C2. 3.2. A Third Row in LSll We will pick a row pair in C2. We will label these two rows rl and r2 and examine characteristics that must be true for a third row which will complete one of the partialtriads of r2}. 11
PAGE 16
Lemma 3.2.1 In LSll, given two rows, rl and r2, that have a partialtriad with elements y, Z, in columns Clo any other row with any of the elements y, or z, in columns Clo or Cl must complete the triad. Proof: Let LS 11 a 23SC latin square of order 11. Let the following table represent rows rl and r2 and columns Clo and Cl, a submatrix of LSI 1. Elements y, and are the elements of a partialtriad. Without loss of generality, let one element, x, appear in r3 in the submatrix. In rl, to preserve latinness, x cannot in CI or C3, so it must appear in C2. Now, because this structure is contained in a 23SC latin square, the x in all and the x in a32 must in a duad or a"triad. To complete a duad there must a yin a31. But this is impossible since there is already a yin CI. SO the x's in all and a32 must in a triad. This implies that the yin al2 must in this triad. Then the y in Clo must in the triad. This implies that r2 is a row of the triad detennined by the x's and so a22 Z must be part of the triad. So y, and Z are the elements in the triad. Since is in the (1,3) position, C3 must the third column in the triad. Therefore the triad must be contained in the structure as shown. 12
PAGE 17
Theorem 3.1.1 Given LS11, a 23SC latin square of order 11 and two rows, r) and r2, in LS11, with {r\, r2} e C2, there cannot be a third row that completes 2 of the partialtriads in {r\,r2}. Proof: Up to isotopy, we may assume that rows r) and r2 are the following: 1 3 4 5 8 9 10 11 2 3 6 4 8 7 11 10 Assume that r3 completes one of the partialtriads in r) and r2, and we may, without loss of generality take it to start as: Now we show that r3 cannot complete any of the other two partialtri1,lds that rl and r2 contain. Row r3 cannot complete all three of the partialtriads of r) and r2 because that would put elements 1 through 9 in the first 9 colwnns. That leaves elements 10 and 11 to go the last 2 columns of r3, which is impossible in a latin square. So we may suppose that r3 completes only two of the three triads as illustrated below. c) C3 C4 Cs C6 C7 Cs CIO CII 2 3 4 6 7 8 10 11 2 3 5 6 4 8 7 11 10 3 2 6 4 By Lemma 3.2.1, none of a37, a38, a39, can be 7, 8, or 9, since this would complete the third triad in rows f) and r2. This leaves only columns CIO and CII to contain these three elements, which is impossible. Therefore no row can complete more than one triad of the three partialtriads in two rows, r) and r2, with {r\, r2} e C2. 13
PAGE 18
Lemma 3.2.2 three elements, y, and z are in a triad, TI. in a 23SC latin square columns Ct. C2, and C3 and rows rl. r2, and r3, then any two of the three elements x, y, and z cannot coexist in another triad or partialtriad outside ofT. cO!ltained in anyone of the three rows rl. r2, and r3. Proof: Let L be a 23SC latin square. Assume there exists such a triad, T. in L. Suppose the x and y in r. are in another partialtriad, PT2 of triad T 2 Let w be the third element of PT 2 In the second row ofPT 2 w cannot be in both columns, c. and C2. SO x must be in column C2 or y must be in column c.. Assume that x is in column C2, then the x in PT 2 must be the one cell (3,2) ofT The elements {x,y,z} make up a partialtriad ofT. in rows r. and r2. By Lemma 3.2.1, al2 = x implies that r3 completes the triad T. and the x in cell (3,2) is part ofT Thus w = z and is in T. and T2 T We reach a similar conclusion ify is in column c Lemma 3.2.3 two elements, x and y, are in a duad, 0., in a 23SC latin square in columns c. and C2, and rows r. and r2, then they cannot coexist in a partialtriad contained in anyone of the two. rows r. and r2. Proof: Let L be a 23SC latin square. Assume there exists such a duad, O. in L. x y y x Suppose the x and yin r. are in a partialtriad, PT2 of triad T 2 Let w be the third element of the PT 2 In the second row ofPT 2 w cannot in both columns, c. and C2. So x must be in column C2 or y must be in column c.. Assume that x is in column C2, then the x in PT 2 must the one in the (2,2) 14
PAGE 19
position of 0,. Then r2 is the second row ofPT 2 Then since the elements {x,y} form a duad in these two rows, w must appear twice in the same column. So the x and y in row r, cannot coexist a partialtriad. Theorem 3.2.2 Given two rows, r, and r2, in LS11, a 23SC latin square of order 11, with {rio r2} C2. Let row r3 complete one of the triads ofr, and r2. Then {r"r3} CI or {r2,r]} Cl. Proof: Up to isotopy, we may asswne that rows r" r2, and r3 are the following: Asswne that {r" r3} C2 and {r2, r3} C2. Then {r"r]} and {r2,r3} both contain three partial triads and one duad. The elements {4, 5, 6} form a partialtriad in {r" r2}. Since the elements {I, 2, 3} form a triad in rows r" r2, and r3, by Theorem 3.2.1, the partialtriad {4, 5, 6} cannot be completed in r3. But there must be some row that completes the partialtriad {4,5,6} of {r" r2}. Then, by Lemma 3.2.2, none of the elements {4,5,6} can coexist in another partialtriad contained in {r" r3} or {r2, r3}. Similarly, the elements of {7,8,9} cannot coexist in a partialtriad in {rio r3} or {r2, r3}. Since {IO, II} are in a duad in {rio r2}, by Lemma 3.2.3 they also cannot appear together in a partial triad in {rio r3} or {r2, r3}. So the two remaining triads in {rio r3} must each contain one element from the set {4,5,6}, one element from the set {7 ,8,9} and one element from the set {10,Il}. The two triads must also be disjoint. Now since 10 and 11 are both in triads the duad in {r" r3} must contain one element from the set {4,5,6} and one element from the set {7,8,9}. We know that one of the partialtriads of {rio r3} is {1,2,3}. Let us call the elements of the two remaining triads {u,v,w} and {x,y,z} and the elements of the duad {a.b}. Now we look at rows {r2, r3}. By the same reasoning above, the duad contained in {r2, r3} must contain one element from the set {4,5,6} and one element from the set {7,8,9}. And similarly, the elements of {u,v,w} cannot be in the same partialtriad, nor can the elements of {x,y,z}, nor 15
PAGE 20
{a,b} since they are duads or partialtriads in {rio r3}. So, again, the duad in {r2, r3} must contain one element from the set {u,v,w} and one element from the set {x,y,z}. It cannot contain any element of the set {a,b}. In summary, the elements of the duads in {rio r3} and {r2, r3} are disjoint and in each of them there is one element of the set {4,5,6} and one element of the set {7,8,9}. We want to examine the elements of the duads. Let {a,b} the duad of {rl, r)} and let {c,d} the duad of {r2, r3}' We may assume a,c {4,5,6}, and b,d {7,8,9}, a::Fc and b::Fd. Since {a,b} is a duad of {rio rl}, a is in the same colwnn ofr) that b is in rl. And since {c,d} is a duad of {r2, r3}, c is in the same colwnn ofr3 that d is in r2. Also, a::Fc, so these are two different colwnns. But b,d {7,8,9} a partialtriad of {rio r2}. Let e the third element of this partialtriad. The element e must appear as shown since {b,d,e} are in a partialtriad of {rio r2}. And now to complete the triad elements {b, d, e} in {r), r2} we have the following. 16
PAGE 21
Since a,c E is in a partialtriad of {rt. r2}, we may let fbe the third element of this partial triad, and it must appear as follows: Now to complete the {a,c,f} partialtriad in {rt. r2} we have the following: At this point we have: CI CIO Cu 1 2 3 b e d a f C 10 2 3 I e d b f C a 10 3 1 2 a C b d Now in {rt. r3}, the elements d and fmust be in a partialtriad since they are in the same column and there can be no other duad than {a,b}. And in {r2' r3} the elements b and fmust also be in a partial triad since they are in the same column and {c,d} is the duad. Either the 10 or the 11 must go in the first open column ofr3. this entry is 10 we have the following. CI CIO Cu 1 2 3 b e d a f 10 2 3 I e d b f a 10 3 2 a c 10 b d This makes 10 the third element in the partialtriad {d,f,10} of {rt. r3} and also the third element of. the partialtriad {b,f,IQ} of {r2, r3}' Completing these partialtriads puts the element fin two positions in r3. 17
PAGE 22
Similarly, we place the 11 in that cell we again get the element f two positions in Thus we see that {cJ, and cannot both be in C2, and therefore at least one them must be Cl. 3.3 Buildinl; Four Rows of LSll We will start again with two cows, rl and with C2 and examine properties of two different rows, and that each complete one triad of {rJ,c2}. Theorem 3.3.1 Given two cows, and in LSll, a 23SCLS of or dec 11, with {rhc2} C2, there exists rows and that each complete one triad of Up to isotopy we may assume that Cit and are as illustrated below. Elements in and have the following properties: i) Columns CIO and CII of must have one and only one element from the set {4,5,6}. ii) Colwnns CIQ and CII ofc3 must have one and only one element from the set {7,8,9}. Columns CIO and CII of must have one and only one element from the set {1,2,3}. iv) Columns CIQ and CII ofc4 must have one and only one element from the set {7,8,9}. v) The elements from the set {7,8,9} in columns CIO and CII ofc3 and cannot be in the same column. vi) The elements from the set {7,8,9} in columns CIO and CII ofc3 and cannot be the same element. CII 1 2 3 4 5 6 7 8 9 10 11 2 3 1 5 6 4 8 9 11 10 3 1 2 6 4 5 18
PAGE 23
Proof: Given that {rhr2} E C2, they contain three triads and one duad. There must exist rows r) and r4 that complete partialtriads of {rhr2} for LSII to 23SC. They cannot the same row by the Theorem 3.2.1. We prove properties (i) through (iv) first. In rows rio r2, and r), to preserve latinness, the only elements that can in cells (3,10) and (3,11) are 4,5,6, 7, 8, or 9. Suppose there are 2 of the elements of the set {4,5,6} in cells (3,10) and (3,11). Let them called x and y respectively. By Lemma 3.2.1 none of {7,8,9} can go in any of cells (3,7), (3,8), or (3,9). Therefore, in row r), they must be in cells (3,4), (3,5), (3,6). Then 10 and 11 must be in cells (3,7), (3,8), or (3,9). We now observe rows rl and r). They contain a partialtriad in elements {I ,2,3}. Cs CII 2 3 4 6 7 8 9 10 11 3 2 x y The element x in cell (3,10) must be in a duad or partialtriad with its mate in r1. The element 10 must be in that subsquare since it is in cell (1,10). Since x is equal to 4,5, or 6, one of the elements in cells (3,4), (3,5), or (3,6) must also be in the subsquare. These elements are from the set {7,8,9}, none of which is the element 10. There are three distinct elements in the subsquare; it must be a triad. So {rl,r)} has two triads, and must be an element ofC2. Cs Cs CII 3 5 6 4 8 9 7 10 3 x y Now we look at {r2,r)}, also with a partialtriad in elements {l,2,3}. The element x in cell (3,10) must be in a duad or triad with its mate in r2. Element 11 must be in the subsquare since it is in cell (2,10), and an element from the set {7,8,9} must also be in the subsquare. Again we have a partialtriad. So {r2,r)} has two partialtriads and must be in C2. We have a contradiction since by the Theorem 3.2.2 we know that {rhr)} and {r2,r)} cannot both be in C2. Therefore, two of the elements from the set {4,5,6} cannot be in cells (3,10) and (3,11). By an analogous argument, two elements from the set {7,8,9} cannot be in cells (3,10) and 19
PAGE 24
(3,11). Since the two elements in cells (3,10) and (3,11) must be from the set {4,5,6,7,8,9} and there cannot two from the set {4,5,6} or two from the set {7,8,9}, there must be one element from each set. The same reasoning shows that there must be one element from the set {1,2,3} and one element from the set {7,8,9} in cells (4,10) and (4,11). This proves properties (i), (ii), (iii), and (iv). Now assume that two elements, x and y, from the set {7,8,9} exist in rows r3 and r4 respectively, both in colwnn Ca, where Ca is either CIO or CII. Since they both appear in the same colwnn, they mustboth appear in a duad or partialtriad in {r3,r4}. Cs c, Cs CII 1 2 3 4 5 6 7 8 9 10 11 2 3 1 5 6 4 8 9 7 11 10 3 1 2 x 6 4 5 By Lemma 3.2.1 and Theorem 3.2.1, they can't appear in columns c" cs, or C9. the elements x and y appear in a duad, then both elements must exist in the same column in one of the columns CI through C6. They cannot, since in each of these columns there is only one open cell. Thus x and y cannot be in a duad in {r3,r4}, so they must in a partialtriad. In row r3, must be in columns Col, Cs, or C6. This implies that an element from the set {4,5,6} must be in the partialtriad. In row r4, x must in columns CI, C2, or C3. This implies that an element from the set {1,2,3} must in the partialtriad. So in the partialtriad we have two different elements from the set {7,8,9} and one element from each of the disjoint sets {l,2,3} and {4,5,6}. This is four elements. Thus we conclude that two of the elements of the set {7,8,9} cannot exist in the same column CIO or CII rows r3 and r4, proving (v). Now assume that one element, from the set {7,8,9} is in the 1011t column ofr3 and the 1111t column of r4. Cs Cs CII 1 2 3 4 5 6 7 8 9 10 11 2 3 1 5 6 4 8 9 7 11 10 3 1 2 x 6 4 5 x 20
PAGE 25
Then the cells (3,10) and (4,11) must be in a duad Of partialtriad. Also the cells (3,11) and (4,10) must be part of this subsquare. The element in cell (3,11) must be from the set by part (i) above and the element in cell (4,10) must be from the set {1,2,3} by part above. Since these two sets are disjoint cells have distinct elements in them and so must be part of a partialtriad. To complete the partialtriad the elements in cells (3,11) and (4,10) must appear the same column of the fOWS f) and f4; i.e. The element from set {1,2,3} in cell (f4,CIO) and the element from the set in cell (f),CII) must appear in the same column of the fOWS f) and f4. But they cannot, since the elements from the set {1,2,3} are all in CI, C2 and c) fOW f); and the elements from the set are all in C4. and C6 Off OW f4. Therefore the elements from the set {7,S,9} in columns CIO arid CII of fOWS f) and f4 cannot be the same element. This proves Using the properties we have discovered to this point we will build four fOWS of LS 11. We know that there exists two fOWS that are in C2. We will call these two fOWS fl and f2. We know that a third and fourth row exists that completes two of the triads of {fl and that they cannot be the same fOW. We call them r3 and r4. We know several othef pfoperties of these rows from Theorem 3.3.1. Up to isotopy we may assume that these four rows are the following: CII 1 2 3 4 6 7 8 9 10 11 2 3 1 6 4 S 9 7 11 10 3 1 2 7 4 6 4 1 8 In f4, the element 7 cannot exist in columns c,. CS, Of CsI by Lemma 3.2.1. Therefore 7 can only exist in columns c .. C2, Of C3. In rows {r3.f4}, 7 must be in a duad or partialtriad with 1 since they are in the same column in those rows. 7 is in CI or C3 of f4 then 7 is in a partialtriad and 2 Of 3 must be in it. This is impossible by Lemma 3.2.2, so 7 can only exist in column C2 of row r4. Similarly 8 can only exist in column of row r3. thus we have the following: 21
PAGE 26
Cs Cs C8 Cll I 2 3 4 6 7 8 10 11 2 3 I 6 4 8 9 7 11 10 3 I 2 8 7 4 7 6 4 I 8 Figure 3.3.1 From the discussion above we have the following lemma. Lemma 3.3.1 In LSII, a 23SC latin square of order 11 there exists four rows isotopic to those in Figure 3.3.1. 3.4 NonExistence of LSll We now show that these four rows of Lemma 3.3.1 cannot completed LSII and thus a 23SC latin square of order 11 does not exist. Theorem 3.4.1 A 23SCLS of order II does not exist. Proof: By Lemma 3.3.1 there exist four rows in LSII isotopic to those in Figure 3.3.1. Given these four rows, we consider the entries in the remaining cells and show that these four rows cannot exist. We consider the placement of9 in r4. It must go in cell (4,1) or (4,3). We consider 9 cell (4,1). Cs Cll 1 2 3 4 6 7 8 10 11 2 3 I 6 4 8 7 11 10 3 1 2 8 7 4 9 7 6 4 1 8 22
PAGE 27
Now observe colwnns c), eg, and CID of rows rl and r4. The l's are not in a duad and so cell (4,9) must contain 10 to form a partialtriad. So we have the following: Cs Cll 2 3 4 6 7 8 9 10 11 2 3 6 4 8 9 7 11 10 3 1 2 8 7 4 9 7 6 4 10 1 8 Now observe columns C7, eg, and CII of rows f2 and r4. The lO's are not in a duad and cell (4,7) must be 7 in order to form a partialtriad. But there is already a 7 in cell (1,7), so we have a contradiction. Thus, 9 cannot be in cell (4,1), and so, must be in cell (4,3). Cs Cs ell 1 2 3 4 6 7 8 9 10 11 2 3 1 6 4 8 9 7 10 3 1 2 8 7 4 7 9 6 4 1 8 23
PAGE 28
Now observe columns C3, Ca, and CIO of rows r2 and r4. The l's are not in a duad and cell (4,8) must 11 to form a partialtriad. CI Cs Ca CIO CII 2 3 4 5 6 7 8 9 10 2 3 1 5 6 4 8 9 7 10 3 1 2 8 7 4 7 9 6 4 1 8 We now will consider where 9 is in r3. must in either (3,4) or (3,6). Ifit is in (3,6) we have: CI Cs C, CIO CII 1 2 3 4 5 6 7 8 10 2 3 1 5 6 4 8 9 7 11 10 3 2 8 9 7 4 7 9 6 4 5 11 1 8 Observe colwims C6, Ca, and CII of rows r2 and r3. The 4's are pot in a duad and cell (3,8) must 10 to form a partialtriad. 24
PAGE 29
Cs CIO C11 1 2 3 4 6 7 8 9 10 11 2 3 1 5 6 4 8 9 7 11 10 3 1 2 8 9 10 7 4 7 9 6 4 5 11 1 8 Observe colWlUlS C7, Cs, and CIO of rows rl and r). The 10'5 are not in a duad and cell (3,7) must 8 to form a partialtriad. But there is already an 8 in cell (2,7), so we have a contradiction. Thus, 9 cannot in cell (3,6), and so, must be in cell (3,4). CI Cs Cs CIO C11 1 2 3 4 6 7 8 10 11 2 3 1 5 6 4 8 9 7 11 3 1 2 9 8 7 4 7 9 6 4 5 1 8 Observe columns C4, eg, and CII of rows rl and r); The 4'5 are not in a duad and cell (3,9) must be 11 to form a partialtriad. We have the following: CI Cs Cs CIO C11 1 2 3 4 5 6 8 9 10 11 2 3 1 5 6 4 8 9 10 3 1 2 9 8 11 4 9 6 4 5 11 1 8 25
PAGE 30
Now, considering latinness, the only element that can exist in cell (4,1) is 10. Also the only element that can exist ceD (3,6) is 10. Cs c, C1l 1 2 3 4 5 6 7 9 10 11 2 3 1 5 6 4 9 7 11 10 3 1 2 9 10 11 7 4 10 7 9 6 4 5 11 1 Notice that in rows r3 andr4, the subsets {1,7} and {4,8} are duads. Then, {r3,r4} E Cl. Then, {r3,r4} contains only one partialtriad. In column C3 there is a 2 and a 9. column C4 there is a 9 and a 6. So elements 2, 6, and 9 must appear in a partialtriad. Column Cl has a 3 and a 10 and column C6 has a 10 and a 5. So elements 3, 5, and 10 must appear in a partialtriad. This gives us a contradiction. Hence this set offour rows cannot exist in a 23SCLS of order 11 and therefore the 23SC latin square LS 11 cannot exist. 26
PAGE 31
4. Higher Orders of SC Latin Squares Heinrich indicates there are no results for 23SC latin squares for orders greater than 12 [I). Possibly some of the concepts presented here could used to help detennine their existence. For order 13 there are two possible configurations for a pair ofrows. Rows ra and rb. with {ra.rb} E CI. have one partialtriad and duads. For {ra rb} E C2. they have three partialtriads and 2 duads. Two rows in CI would isotopic to the two rows of Figure 4.1. while two rows in C2 would isotopic to two rows of Figure 4.2. Figure 4.1 I have run a program to get the all the possible three line configurations starting with the following two sets S\, illustrated in Figure 4.3 and 8 in Figure 4.4. 1 3 4 6 7 8 9 10 11 12 13 3 4 7 6 9 8 11 10 13 12 3 1 2 Figure 4.3 2 3 4 6 8 9 10 11 12 2 3 1 4 6 9 8 11 10 13 12 3 1 2 Figure 4.4 27
PAGE 32
My program found 320 starting positions using SJ which I was able to reduce to 4 through isotopy. and 722 for S2. which are much more difficult to reduce by isotopy. I have only been able to eliminate Bill Cherowitzo has run some of these starting positions through his program but has yet to find a 23SC latin square. To test one takes about 20 minutes.
PAGE 33
BIBLIOGRAPHY [IJ K. Heinrich, 1991. Latin Squares With and Without Subsquares of Prescribed Type, 46, Elsevier Science Publishers B.V., New York, 101147. [2J K. Heinrich and W. D. Wallis, 1981. The Maximum Number of Intercalates in a Latin Square, Springer Verlag, Berlin, 221233. [3J F. P. Hiner and R B. KiUgrove, 1970. Subsquare Complete Latin Squares, 758. [4] R B. Killgrove, 1964. Completions of Quadrangles in Projective Planes, 16, 6376 [5J R Killgrove and E. Milne, 1974. Subsquare Complete Latin Squares of Order 12, Proc. Fifth S.E. Conf. On Combinatorics, Graph Theory, and Computing, 547. 29
