tailieunhanh - Báo cáo toán học: "A Generalisation of Transversals for Latin Squares'

Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí toán học quốc tế đề tài: A Generalisation of Transversals for Latin Squares. | A Generalisation of Transversals for Latin Squares Ian M. Wanless Christ Church St Aldates Oxford OX1 1DP United Kingdom wanless@ We define a k-plex to be a partial latin square of order n containing kn entries such that exactly k entries lie in each row and column and each of n symbols occurs exactly k times. A transversal of a latin square corresponds to the case k 1. For k n 4 we prove that not all k-plexes are completable to latin squares. Certain latin squares including the Cayley tables of many groups are shown to contain no 2c 1 -plex for any integer c. However Cayley tables of soluble groups have a 2c-plex for each possible c. We conjecture that this is true for all latin squares and conhrm this for orders n 8. Finally we demonstrate the existence of indivisible k-plexes meaning that they contain no c-plex for 1 c k. Submitted September 5 2001 Accepted March 18 2002. MR Subject Classification 05B15 1. Introduction A partial latin square of order n is a matrix of order n in which each cell is either blank or contains one of 1 2 . ng or some other hxed set of cardinality n and which has the property that no symbol occurs twice within any row or column. A cell which is not blank is said to be filled. A partial latin square with every cell filled is a latin square. The set of partial latin squares of order n is denoted by PLS n and the set of latin squares of order n by LS n . We say that P1 2 PLS n contains P2 2 PLS n if every filled cell of P2 agrees with the corresponding cell of P1. P 2 PLS n is said to be completable if there is some L 2 LS n such that L contains P. On the other hand P is said to be maximal if the only partial latin square which contains P is P itself. We coin the name k-plex of order n for a K 2 PLS n in which each row and column of K contains exactly k filled cells and each symbol occurs exactly k times in K. The entries on a transversal of a latin square form a 1-plex. In the statistical literature eg. Finney 10-12 a .