koorio.com

海量文库 文档专家

海量文库 文档专家

- Latin squares, partial latin squares and its generalized quotients
- A SOLUTION FOR THE EMBEDDING PROBLEM FOR PARTIAL TRANSITIVE TRIPLE SYSTEMS
- COMPLETING PARTIAL LATIN SQUARES WITH PRESCRIBED DIAGONALS
- ROBUST SOLUTIONS TO LEAST-SQUARES PROBLEMS WITH UNCERTAIN DATA
- FastSLAM A factored solution to the simultaneous localization and mapping problem
- A partial solution of the isoperimetric problem for the Heisenberg group
- An Introduction to Partial Least Squares describes
- A solution to a problem of Fermat, on two numbers of which the sum is a square and the sum
- Embedding graphs in books a layout problem with applications to VLSI design
- An IMMPDAF Solution to Benchmark Problem for Tracking in Clutter and Standoff Jammer

A SOLUTION TO THE EMBEDDING PROBLEM FOR PARTIAL IDEMPOTENT LATIN SQUARES

L. D. ANDERSEN, A. J. W. HILTON AND C. A. RODGER

1. Introduction A partial latin square on t symbols <rl5..., ut of side n is an n x n matrix, each of the cells of which may be empty or may be occupied by. one of the symbols ol,..., at, and which satisfies the rule that no symbol occurs more than once in any row or more than once in any column. An incomplete latin square on t symbols of side n is a partial latin square in which there are no empty cells; it is a latin square of side n if t = n. In a partial latin square of side n on t symbols a1,...,at, if cell (i,i) is occupied by symbol <r, for each i, 1 < i < n, then the partial latin square is idempotent. The object of this paper is to prove the following theorem.

THEOREM 1. A partial idempotent latin square R of side n ^ 1 on the symbols ot,...,on can be embedded in an idempotent latin square of side t on the symbols ax,..., otfor each t ^ 2n +1. The lower bound 2n + \ for t is best possible.

This problem has quite a long history. In 1960 Evans [6] showed that a partial latin square of side n on n symbols could be embedded in a latin square of side t for all t ^ In. In 1971 Lindner [10] showed that a partial idempotent latin square R could be embedded in an idempotent latin square; his containing square had side ^ c2{2"\ for some constant c. In 1973 Hilton [8] showed that the idempotent embedding is possible for t = 4(n + k), k = 0 , 1 , 2 , . . . , or t ^ 8n + l and posed a conjecture, now proved as Theorem 1 of this paper. Recently Andersen [2] improved Hilton's result by showing that the idempotent embedding is possible for all t ^ 4n, t jz 4n + 1 . In the survey of embedding theorems for partial designs and algebras by Lindner and Evans [11], Lindner wrote, of the partial idempotent latin square embedding problem, "after years of anguish, the author is still running around in circles on this problem (and so is Allan Cruse)". The attraction of this problem, apart from the difficulty of finding a proof, lies in the fact that idempotency appears at first sight to be the simplest of rules. But in fact some other requirements, symmetry (commutativity) for example, have turned out to be much more manageable (see [5, 11]). We now give some of the ideas and results we need for the proof. Let T be a t x t matrix containing a n r x s submatrix S in the top left hand corner, where r ^ s. The

set {(r-f-1,5+1), (r + 2,s + 2),..., (n — s + r, n)} is called the (s — r)-th upper diagonal of

T outside S. We shall use the following theorem [3, 4].

T H E O R E M 2. the symbols aY,..., Let t ^ s ^ r > 0 . Let <xt and let S be placed S be an incomplete rxs latin rectangle of a matrix on

in the top left hand corner

T, all of

Received 12 June, 1981. J. London Math. Soc. (2), 26 (1982), 21-27

22

L. D. ANDERSEN, A. J. W. HILTON AND C. A. RODGER

the cells ofT outside S being empty. Let f be a non-negative integer valued function on {ax, ...,o",} such that , ft-s-1 ifr = s,

I f(0i) <

i= 1

{ t-s

ifr^s.

Then T can be filled in to form a latin square in which the symbol a{ occurs at least /((T,) times on the {s — r)-th upper diagonal outside S if and only if av (1 < i ^ t) occurs

at least r + s — ?+/(<T,) times in S.

The requirement that

i l

?

;=i

/(CT,-)

^ t — s — 1 if r = s cannot be improved to

at

f(ai) ^ l~s

( s e e W)- This ^ e s

^

e core

°^ ^

e

difficulty that has been

experienced in finding a proof of Theorem 1. We shall also use the following theorems [8, 7].

THEOREM 3. An idempotent latin square of side n ^ 1 can be embedded in an idempotent latin square of order t for all t ^ In +1. THEOREM 4. An incomplete nxr completed to an nxn latin square. latin rectangle on symbols ax,...,an can be

If G is a graph with vertex set V(G) and edge set E(G), then an edge-colouring of G is a map </>: E(G) -> C, where C is a set of colours, such that $ ( e j ^ $(e 2 ) if e t and e2 have a common vertex. Konig [9] showed that a bipartite graph G with maximum degree A(G) has an edge-colouring provided that \C\, the number of colours, is at least A(G). Finally we remark that the more general problem of embedding an incomplete latin square in a latin square with prescribed diagonal will be considered in a forthcoming paper by C. Rodger. There are a number of additional complications which can arise in the general case.

2. Proof of Theorem 1 In view of Theorem 3, we may assume that R has at least one empty cell. The only maximal partial idempotent latin squares of orders one, two and three are

G

<?3

2

to"

<*3

n

2

°2

^3

Since there exist idempotent latin squares of all orders greater than 2, Theorem 1 is true for n = 1 and 2. By Theorem 3, Theorem 1 is true for n = 3. We shall assume from now on that n ^ 4.

A SOLUTION TO THE EMBEDDING PROBLEM

23

We begin by filling the empty cells of R using only the symbols <Tn + i,...,a2n-iSince R is idempotent, each row and column of R contains at most n — 1 empty cells. Form a bipartite graph G with vertex sets {px,..., pn} and {cx,..., cn}, and join px to Cj by an edge if and only if the cell (i,j) of R is empty. Then G has maximum degree at most n — \ and so, by Konig's theorem, we can give it an edge-colouring with colours o'n + x,...,o'2n_x. Now fill cell (i,j) of/? with the symbol an+k if and only if the edge (ph Cj) is coloured with o'n+k. By the edge-colouring of G, no symbol occurs more than once in any row or column of R. We shall now enlarge R to an (n +1) x (n + 2) incomplete latin rectangle R* by adding a zeroth row p0 and two columns, namely c_x and c 0 . As a preliminary step to embedding R in T, we shall embed JR* in a t x t latin square T* on symbols ax,..., at, with rows p0,..., pt_x and columns c_x,c0, c l 5 ..., c r _ 2 , in which the cells (n + 1, n + 1), (n + 2, n + 2),..., (t — 2, t — 2) are filled with the symbols on + x,..., at-2 respectively and in which cells (pojC.J, (po,co), (pi,c^1), {px,c0) are filled with crt_l5 at, ut, <?,_! respectively. See Figure 1.

Po

C_

FIG.

1. The

square T

In order that /?* may satisfy the condition of Theorem 2, p 0 , c_ t and c0 must be filled in such a way as to ensure that each of the symbols alt..., an, ot-x, at occurs at

24

L. D. ANDERSEN, A. J. W. HILTON AND C. A. RODGER

least (n + \) + (n + 2) — t = 2n + 3 — t times and each of the symbols an + l,..., occurs at least 2n + 4 — t times in R*.

LEMMA.

at.2

For t ^ 2n + \, R* can be filled so that In + 3 — t if 1 ^ i ^ n or i = t — \ or t,

JVfo) ^

2n + 4-t where

N(<T,)

ifn + \ ^ i ^

t-2,

is the number of times o^ occurs in R*.

Proof First we consider the case when t = 2n + l, the other cases following easily from this case. For this case we have to show that R* can be filled in so that R~ be the (n — \)xn incomplete latin rectangle on ol,...,o2n-i consisting of rows p2,...,pn of R. If exactly one of the symbols on + l,..., a2n-1 does not occur in R~, let the notation be chosen so that this symbol is o2n_x. We first fill in rows p2,..., pn of column c0 as follows. Form a bipartite graph G' with vertex sets {p2,..., pn, p*} and {alt..., <72n-i}- J ° m Pi t 0 <*j by an edge if and only if the symbol o} does not occur in row p,- of R~ and join p* to a} if and only if n+\ ^ j ' ^ 2n— 1 and a} occurs exactly once in R~. Then the degree d(Oj) of ex, in G' will be n— 1 if a, does not occur in R~ or if n +1 ^ j' ^ 2n — 1 andCTJoccurs once in R~. In general, rf(ff;) ^ n —1. Similarly rf(p,) = n — 1 since there are n — 1 of the symbols ax,..., o2n_x missing from row p{. Finally, d(p*) ^ n — \ since there are n — 1 integers j such that n +1 ^ _/ ^ 2n — 1. By Konig's theorem, this graph can be edge-coloured with n — 1 colours. If dip*) < n — 1, let K be a colour which does not occur on any edge incident with the vertex p*, and if d(p*) = n — 1, (that is, if each of on + l,..., o2n_x occurs exactly once in /?"), let K be the colour of the edge p*oln_i. Fill c0 by placing the symbol Oj in row p, of column c0 if and only if a^ is joined to p, by an edge of colour K. Any symbol that does not occur in R~ will have degree n— 1 in G' and so will have an edge of colour K on it, and will therefore be placed in c 0 . Similarly, unless all of the occur exactly once in R~, those of these symbols which symbols an+\,...,o2n-\ occur at least once in R~ now occur at least twice in R~ u c 0 . In this exceptional case, which corresponds to the case when d(p*) = n-1, each of the symbols an + j , . . . , oln-2 occurs twice in R~ u c 0 , whereas the symbol oln-i occurs just once in R~ u c 0 . Now in the case when there is a j such that n+\ ^ j ^ 2n — 2 and o} occurs exactly twice in R~ u c 0 , we may assume that <J2n-2 occurs exactly twice in R~ u c 0 . We next fill in rows p 2 , . . . , pn of column c ^ . We form a bipartite graph G" with the same vertex sets as G'. We join p, to o} if and only if a-} does not occur in row p, of R~ u c 0 , and we join p* to Oj if and only if either n+\ ^ j ^ 2n — 2 and o^ occurs twice in R~ u c 0 or _/ = 2n—1, <7j occurs twice in R~ u c 0 and there is some / , n + 1 < / ^ 2/i — 1, such that <jf does not occur twice in R~ u c 0 . Then the degree d{p*) of p* in G" is at most n — 2. Similarly d(a}) ^ n — 2 (1 ^ 7 ^ 2n —1) since a,occurs at least once in R~ u c 0 . Also rf(p,-) = n — 2 since there are exactly n — 2 of CT15 ..., <72n-i which do not occur in row p,. By Konig's theorem, G" can be edgecoloured by n — 2 colours. If d(p*) < n — 2, let K be a colour not on any edge incident

JV(<T,) ^ 2 if 1 ^ i! ^ n or i = t-1 or t, N(^) immediately that NIG,.^ = N(at) = 2. Let ^ 3 if n +1 ^ i ^ 2n-1. We observe

A SOLUTION TO THE EMBEDDING PROBLEM

25

with p* and if d(p*) = n-2 (that is, if at least n-2 of <r n+1 ,..., a 2 n-i occur exactly twice in R~ u c0), let K be the colour of the edge p*G2n-i ^ t m s e dge i s m G", D u t otherwise use the colour of the edge p*G2n-2. Fill column c_ x of R* by placing the symbol a,- in row p ; of column c_ x if and only if the vertex a} is joined to p, by an edge coloured K. Since any symbol that occurred once in R" u c0 is placed in column c_ 1 ; every symbol now occurs at least twice in R~ u c , u c 0 . If two or more of the symbols °n + i> ???> a2n-i do not occur in R" then the degree of p* in both G' and G" is at most n —3, and so those of these symbols which do occur in R~ will occur three times in R~ u c . ( u c 0 . Thus we have the following possibility. (1) Two or more of the symbols <xn + 1 ,..., o"2n_1 do not occur in R~ and now occur exactly twice in R~ u c_ x u c 0 , while the rest of these symbols now occur at least three times in R~ u c . ( u c 0 . Also each of ax,..., an occurs at least twice in

R~ KJ C_j U C o .

If exactly one of the symbols on + x,..., oln_x does not occur in R~ then we assumed earlier that the missing symbol was o2n-x. If a t most one of the symbols on + x,..., oln-\ does not occur in R~, then each of the symbols on + x,..., c 2 n _ 3 occurs at least three times in R~ u c_! u c 0 and both <72n_2 and o2n-\ occur at least twice in R~ u c_ x u c 0 . Thus we have the following second possibility. (2) Each of o" n+1 ,..., <J2rI-2 occurs at least once in R~, whilst the symbol <r2n_1 may or may not occur there. In R~ u c_j u c 0 , each of an + l,..., o-2n_3 occurs at least three times and each of ox,..., an, cr 2n - 2 , o-2n_! occurs at least twice in

R~ U C_! U

Co.

To fill p 0 in case (1), form a bipartite graph G* with vertex sets {c 0 ,..., cn} and { 7 j , . . . , <72n-i} and join c,- to a} if and only if a^ does not occur in the column c{ of R. < Clearly the degree d(ct) of c, in G* is n —1 (1 ^ i < n). Some of the vertices Gj for n + 1 ^ ; " ^ 2n —1 may have degree n, but because R is idempotent, each of the vertices ol,...,(rn has degree at most n — \. Since R originally had at least one empty cell, at least one of the vertices al}..., an, say ox, has degree at least one. Place ox in row p 0 in a column from which it is missing in R, say column cn. Remove the vertex cn and all edges incident with cn from G*, giving a modified graph G*'. Then, because all vertices a} of degree n were adjacent to cn, the degree d'{a}) in the modified graph G*' is at most n - 1 {\ ^ j ^ 2n-l); also d V i ) ^ ? - 2 and d'(c,) = n - l (1 ^ i ^ n—1). Colour the edges of G*' with n — \ colours and use a colour that is not on any edge incident with ax to complete the row p 0 in the same manner as described earlier. Since any symbol Oj which does not occur in R has degree n — 1 in G*', it is used in p 0 , and so the symbols on + x,..., o2n_x each occur at least three times in R*. To fill p 0 in case (2) we consider two possibilities. (2a) in R. Each of an + x,..., <T2n_2 occurs at least once in R, but o2n_x does not occur

We form the bipartite graph G* as above. Then d(c{) = n — 1 (1 ^ i ^ n), d{a}) ^ n — 1 (1 ^ 7 ^ 2n — 2) and d(o-2n_i) = n. If a 2n _ 2 occurs at

26

L. D. ANDERSEN, A. J. W. HILTON AND C. A. RODGER

least three times in R u c_x u c 0 then we delete one edge on o2n-i> say the edge c1<r2n-i> edge-colour G*\{c 1 <r 2n _ 1 } with n — \ colours and use the colour K of an edge incident with cx to fill p 0 in the usual way. If G2n-2 occurs only twice in R u c_ x u c 0 , then d{o2n_2) ^ n — 2 and so there is a vertex, say cx, which is joined in G* to both <r2n_2 and G2n-X. Delete the edge c1o2n_1 and edge colour G*\{ c i°"2n-i} with n — \ colours. Let K be the colour of the edge cxG2n_2 and use K to fill p 0 in the usual way. Then all of the symbols Gn + X,..., a 2n _ 1 will occur at least three times in R*. The other possibility is as follows. (2b) Each of Gn+X,..., o2n-i occurs at least once in R.

We form a bipartite graph Gt with vertex sets {c l 5 ..., cn, c*} and {GX,..., G2n_x}, joining c, to o^- if and only if the symbol a} does not occur in column ch and joining c* to Gj if and only if; = In — 2 or In — 1 and IT,- occurs exactly twice in /?. Then the degree d{c) of c,- in Gf is n — 1 (1 ^ i: ^ n), d(c*) ^ 2 and, since the symbols Gj (1 < j ^ 2n— 1) each occur at least once in R, d{a}) < n—1 (1 < j < 2n— 1). If <72n_2 or <72n_j occurs twice in R u c_ t u c0 then its degree is n — \. Colour Gf with n — \ colours and use a colour K which does not occur on c* to fill p 0 in the usual way. Such a colour exists since n — \ ^ 3 > 2 ^ d{c*). Then o" n+x ,..., o-2n- I a ^ o c c u r at least three times in R*. This completes the proof of the lemma when t = In +1. If t = 2n + 2 we have to show that R* can be filled in with symbols GV, ..., G, SO that N(ff,) ^ 1 if 1 s$; ^ n or j = t-\ or j = t, and so that N(Gj) ^ 2 if n + 1 ^ j ^ 2n. Consider the filling in of R* just achieved in the case when t = 2H + 1. There both <x2n_2 and o2n_x each occurred at least three times. Replace Gln and G2n + i in R* by G2n + l andff2n+ 2 respectively. Select a cell c containing the symbol G2n_2 and replace <72n_2 by G2n. Select a cell containing ff2n_i in a different row and a different column from c, and replace o-2n_1 by a 2n . Then R* now satisfies the requirement for the case when t = 2n + 2. If t = 2n + 3 we have to show that R* can be filled in with symbols GX, ..., G, SO that A^Oy) ^ 1 if n +1 ^ j ^ 2n +1. Consider the filling in of R* just achieved in the case when t = 2n + 2. There, o2n occurs twice. Replace o2n + i a n d a2n + 2 in R* by a 2n + 2 anc ^ °"2n + 3 respectively and replace G2n in one of the cells which contain it by G2n + l. Then R* satisfies the requirement for the case when t = 2n + 3. If t ^ 2n + 4 we merely have to show that R* can be filled in with symbols GX, ..., Gt. Then the original R* will suffice if we replace <x2n and G2n + X by t7r_, and CT, respectively. This completes the proof of the lemma. We now resume the proof of Theorem 1. By Theorem 2 we embed R* in a t x t latin square T* on symbols GX, ..., G, as described earlier. We remove rows p0 and p t _j and columns c_x and c 0 forming a (t — 2)x(? — 2) incomplete latin square T', and to T we shall adjoin a new row pt_x and a row p, and columns cr_j and c, so as to make an idempotent latin square T, embedding R. To fill columns c l 9 ..., c,_ 2 of the final two rows, form a bipartite graph Go with vertex sets {cx,..., c t _ 2 } and {GX, ..., <7f}, and join ct to (7,- if and only if Gj does not occur in column c, of T'. The maximum degree in Go is two, and so Go is the disjoint union of paths and even circuits, the paths having all their end vertices amongst

A SOLUTION TO THE EMBEDDING PROBLEM

27

a!,..., or The symbols at.x and at both occur t — 3 times in T , and so the degrees of at_x and cr in Go are both 1. If we identify the vertices ot-^ and at we obtain a bipartite graph of maximum degree 2 and this can be edge-coloured with two colours. This corresponds to an edge-colouring of Go with two colours in which the edge on c,_ x and the edge on at receive different colours. Use the edges of one colour to fill row p,_ x and the edges of the other colour to fill row pt, placing a symbol o} in column ct of the relevant row if the edge c^j receives the relevant colour; do this in such a way that the symbol at_l is placed in row pt and the symbol at is placed in Finally complete the latin square T by Theorem 4 and permute the final two columns, if necessary, so that the two missing symbols of p l 5 namely at^1 and at, are placed in columns ct and ct.l respectively. Then it automatically follows that at_1

and at occur in cells (p ( _ lf c,_J and {pt, ct) respectively. This proves Theorem 1.

References

1. L. D. ANDERSEN, 'Latin squares and their generalizations', Ph.D. Thesis, University of Reading, 1979. 2. L. D. ANDERSEN, 'Embedding latin squares with prescribed diagonal', Theory and practice of combinatorics (eds. A. Rosa et al, North Holland, Amsterdam), to appear.

3. L. D. ANDERSEN, R. HAGGKVIST, A. J. W. HILTON and W. B. POUCHER, 'Embedding incomplete latin

4. 5. 6. 7. 8. 9. 10. 11.

squares in latin squares whose diagonal is almost completely prescribed', European J. Combin., 1 (1980), 5-7. L. D. ANDERSEN and A. J. W. HILTON, 'Thank Evans!', preprint, University of Reading, 1979. A. B. CRUSE, 'On embedding incomplete symmetric latin squares', J. Combin. Theory Ser. A, 16 (1974), 18-22. T. EVANS, 'Embedding incomplete latin squares', Amer. Math. Monthly, 67 (1960), 958-961. M. HALL, JR., 'An existence theorem for latin squares', Bull. Amer. Math. Soc, 51 (1945), 387-388. A. J. W. HILTON, 'Embedding an incomplete diagonal latin square in a complete diagonal latin square', J. Combin. Theory Ser. A, 15 (1973), 121-128. D. K.ONIG, Theorie der endlichen und unendlichen Graphen (Chelsea, New York, 1950). C.C.LINDNER, 'Embedding partial idempotent latin squares', J. Combin. Theory Ser. A, 10 (1971), 240-245. C. C. LINDNER and T. EVANS, Finite embedding theorems for partial designs and algebras, Collection Seminaire de Mathematiques Superieures 56 (Les Presses de l'Universite de Montreal, Montreal, 1977).

Department of Mathematics, The University of Reading, Whiteknights, Reading RG6 2AX.