Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: Latin squares with forbidden entries. | Latin squares with forbidden entries Jonathan Cutler Department of Mathematics University of Nebraska-Lincoln Lincoln NE 68588-0130 USA jcutler2@ Lars-Daniel Ohman Department of Mathematics and Mathematical Statistics Umeả University SE-901 87 Umeả Sweden Submitted Jan 16 2006 Accepted Apr 17 2006 Published May 12 2006 Mathematics Subject Classifications 05B15 05C70 Abstract An n X n array is avoidable if there exists a Latin square which differs from the array in every cell. The main aim of this paper is to present a generalization of a result of Chetwynd and Rhodes involving avoiding arrays with multiple entries in each cell. They proved a result regarding arrays with at most two entries in each cell and we generalize their method to obtain a similar result for arrays with arbitrarily many entries per cell. In particular we prove that if m 2 N there exists an N N m such that if F is an N X N array with at most m entries in each cell then F is avoidable. 1 Introduction The study of avoiding given configurations in Latin squares was initiated by Haggkvist who in 1989 asked which n X n arrays can be avoided in every cell by some n X n Latin square. While finding arrays which cannot be avoided has some merit finding families which can be avoided seems to be a more difficult problem. Haggkvist 10 was the first to present such a positive result Theorem 1 below . Throughout the paper we shall use the notation n for the set 1 2 ng. Unless explicitly stated otherwise an n X n Latin square uses symbols n . A partial n X n column-Latin square on n is an array of n rows and n columns in which each cell is empty or contains one symbol from n and every symbol appears at most once in each column. THE ELECTRONIC JOURNAL OF COMBINATORICS 13 2006 R47 1 Theorem 1 Let n 2k and P be a partial n X n column-Latin square on n with empty last column. Then there exists an n X n Latin square on the same symbols which differs from P in every cell. .
