Tuyển tập các báo cáo nghiên cứu khoa học trên tạp chí toán học quốc tế đề tài: Perfect factorisations of bipartite graphs and Latin squares without proper subrectangles. | Perfect factorisations of bipartite graphs and Latin squares without proper subrectangles I. M. Wanless Department of Mathematics and Statistics University of Melbourne Parkville Vic 3052 Australia ianw@ Submitted November 16 1998 Accepted January 22 1999. AMS Classifications 05B15 05C70. A Latin square is pan-Hamiltonian if every pair of rows forms a single cycle. Such squares are related to perfect 1-factorisations of the complete bipartite graph. A square is atomic if every conjugate is pan-Hamiltonian. These squares are indivisible in a strong sense - they have no proper subrectangles. We give some existence results and a catalogue for small orders. In the process we identify all the perfect 1-factorisations of Kn n for n 9 and count the Latin squares of order 9 without proper subsquares. 1. Introduction For k n a k X n Latin rectangle is a k X n matrix of entries chosen from some set of symbols of cardinality n such that no symbol is duplicated within any row or any column. Typically we assume that the symbol set is 1 2 . ng. We use L k n for the set of k X n Latin rectangles. Elements of L n n are called Latin squares of order n. The symbol in row r column c of a Latin rectangle R is denoted by Rrc. A Latin square S is idempotent if Sii i for each i. If the symbol set of a Latin rectangle R is 1 2 . ng then each row r is the image of some permutation ơr of that set. That is Rri ơr i . Moreover each pair of rows r s defines a permutation by ơr s ơrơ ỵ. Naturally ơr s ơ g. Any of these permutations may be written as a product of disjoint cycles in the standard way. If this product consists of a single factor we call the permutation a full cycle permutation. A subrectangle of a Latin rectangle is a submatrix not necessarily consisting of adjacent entries which is itself a Latin rectangle. If it happens to be a Latin square it is called a subsquare. An a X b subrectangle of a k X n Latin rectangle is proper provided we have the strict .
