Đang chuẩn bị liên kết để tải về tài liệu:
Báo cáo toán học: " Completing partial Latin squares with two filled rows and two filled columns"

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: Completing partial Latin squares with two filled rows and two filled columns. | Completing partial Latin squares with two filled rows and two filled columns Peter Adams Darryn Bryant and Melinda Buchanan pa@maths.uq.edu.au db@maths.uq.edu.au m.buchanan@uq.edu.au Department of Mathematics University of Queensland QLD 4072 Australia Submitted Jul 16 2007 Accepted Apr 8 2008 Published Apr 18 2008 Mathematics Subject Classification 05B15 Abstract It is shown that any partial Latin square of order at least six which consists of two filled rows and two filled columns can be completed. 1 Introduction Problems concerning the completion of partial Latin squares are notoriously difficult. It is known that deciding whether an arbitrary partial Latin square has a completion is NP-complete 4 . Several classical results in the field concern completability for large families of partial Latin squares. Historically one of the most significant of these is encapsulated by Evans Conjecture posed in 1960 by Trevor Evans 5 . Smetaniuk published a proof of the conjecture in 1981 12 . Theorem 1.1 12 Any partial Latin square of order n with at most n 1 filled cells is completable. Smetaniuk s result completed Lindner s partial proof of 1970 9 . Several other partial results were published notably by Marica and Schonheim 10 and Haggkvist 6 . In 1983 Andersen and Hilton 1 published an alternative proof. Their paper includes the stronger result stated in Theorem 1.2 of the necessary and sufficient conditions for a partial Latin square of order n to be completed if at most n cells are filled. Theorem 1.2 1 A partial Latin square of order n with at most n filled cells is completable if and only if it is not isotopic to one of the partial Latin squares in the figure below. THE ELECTRONIC JOURNAL OF COMBINATORICS 15 2008 R56 1 1 2 x x 1 x 1 In 1945 M. Hall 7 established the following result using P. Hall s Theorem 8 on the existence of systems of distinct representatives of subsets. Theorem 1.3 7 Any partial Latin square of order n consisting of r filled rows r n can be .