Tuyển tập các báo cáo nghiên cứu khoa học hay nhất của tạp chí toán học quốc tế đề tài: Maximising the permanent of (0,1)-matrices and the number of extensions of Latin rectangles. | Maximising the permanent of 0 1 -matrices and the number of extensions of Latin rectangles B. D. McKay and I. M. Wanless Department of Computer Science Australian National University Canberra ACT 0200 Australia bdm@ imw@ Submitted February 18 1997 Accepted March 15 1997 Received in final form February 8 1998. AMS Classifications 15A15 05C70 05B15. Let k 2 m 5 and n mk be integers. By finding bounds for certain rook polynomials we identify the k X n Latin rectangles with the most extensions to k 1 X n Latin rectangles. Equivalently we find the n k -regular subgraphs of Kn n which have the greatest number of perfect matchings and the 0 1 -matrices with exactly k zeroes in every row and column which maximise the permanent. Without the restriction on n being a multiple of k we solve the above problem and the corresponding minimisation problem for k 2. We also provide some computational results for small values of n and k. Our results partially settle two open problems of Minc and conjectures by Merriell and Godsil and McKay. 1. The problem Let k and n be positive integers with k n. A k X n Latin rectangle is a k X n matrix of entries from 1 2 . ng such that no entry is duplicated within any row or any column. We use L k n for the set of k X n Latin rectangles. For R 2 L k n define E R to be the number of R0 2 L k 1 n such that the first k rows of R0 are identical to the corresponding rows of R. We say that E R is the number of extensions of R. We call R1 2 L k n a maximising rectangle if E R1 E R for every R 2 L k n . We define Mk n E R1 for a maximising R1. Similarly we call R2 2 L k n a minimising rectangle if E R2 E R for every R 2 L k n and define mk n E R2 for a minimising R2. We are interested in identifying maximising and minimising rectangles and in finding estimates for Mk n and mk n. In particular we concentrate on maximising rectangles in the case when n mk for some integer m. The problem has at least two other guises which are .
