The intricacy of avoiding arrays is 2

Lars-Daniel Öhman

Department of Mathematics and Mathematical Statistics, Umeå University, SE-901 87, Umeå Sweden

Abstract

Let A be any n × n array on the symbols [n], with at most one symbol in each cell. An n × n Latin square L avoids A if all entries in L differ from the corresponding entries in A. If A is split into two arrays B and C in a special way, there are Latin squares L_{B} and L_{C} avoiding B and C respectively. In other words, the intricacy of avoiding arrays is 2, the number of arrays into which A has to be split.

Key words: Latin square, intricacy, array 1991 MSC: 05B15

1 The theorem

The concept of intricacy (for completing partial Latin squares) was introduced by Daykin and Häggkvist in [2], and a sample of applications to other problems can be found in [3]. An array A is avoidable iff there is a Latin square L that differs from A in every cell. For the problem at hand, the intricacy is the natural number that answers the following question: “If we want to split an array into avoidable arrays, what is the maximum number of arrays we need to use?” In [1] it is proven that this number is at most 3.

There are unavoidable arrays, for example any array containing a whole row or column of just one symbol, so the intricacy is not 1.

Theorem 1 The intricacy of avoiding arrays is 2.

PROOF. Let A be any n × n array on the symbols [n]. Split A into arrays B and C, so that C is empty. Certainly, there is a Latin square L_{C} avoiding C. For each cell in B, move the entry to array C iff it differs from the corresponding entry in L_{C}. Then L_{C} will still avoid C, and the entries left in B form a partial Latin square, which is completable (to L_{C}, for instance). By Theorem 2.1 in

Preprint submitted to Elsevier Science 18 November 2005

[1] B is avoidable, and is avoided by some Latin square L_{B}, which in fact is L_{C} with symbols permuted without fixed points.

References

[1] A. G. Chetwynd, S. J. Rhodes, Avoiding partial Latin squares and intricacy, Discrete Math. 177 (1997), pp. 17–32.

[2] D. E. Daykin, R. Häggkvist, Problem 6347, Amer. Math. Monthly 88 (1981) p. 446.

[3] W. E. Opencomb, On the intricacy of combinatorial construction problems, Discrete Math. 50 (1984), pp. 71–97.