tailieunhanh - Báo cáo toán học: "† Pairs of disjoint q-element subsets far from each other"

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: † Pairs of disjoint q-element subsets far from each other. | Pairs of disjoint q-element subsets far from each other Hikoe Enomoto Department of Mathematics Keio University 3-14-1 Hiyoshi Kohoku-Ku Yokohama 223 Japan enomoto@ Gyula . Katona Alfred Renyi Institute of Mathematics HAS Budapest . 127 H-1364 Hungary ohkatona@ July 27 2001 Abstract Let n and q be given integers and X a finite set with n elements. The following theorem is proved for n n0 q . The family of all q-element subsets of X can be partitioned into disjoint pairs except possibly one if Q is odd so that I Al n A2 B1 n B2 q IA1 n B2 B1 n A2 q holds for any two such pairs A1 B1 and A2 B2 . This is a sharpening of a theorem in 2 . It is also shown that this is a coding type problem and several problems of similar nature are posed. 1 Introduction The following theorem was proved in 2 . Theorem Let X n and 2 k q. The family of all q-element subsets of X can be partitioned into unordered pairs except possibly one if n is odd so that paired q-element subsets are disjoint and if A1 B1 and A2 B2 are two such pairs with A1 n A2 k then B1 n B2 k provided n n0 k q . AMS Subject classification Primary 05B30 Secondary 05C45 94B99. Keywords design Hamiltonian cycle code. iThe work was supported by the Japan Society for the Promotion of Science Grant-in-Aid for Scientific Research B 10440032 the Hungarian National Foundation for Scientific Research grant numbers T029255 DIMACS and UVO-ROSTE THE ELECTRONIC JOURNAL OF COMBINATORICS 8 no. 2 2001 R7 1 The main aim of the present paper is to give a sharpening of this theorem. Dehne the closeness of the pairs A1 B1 and A2 B2 by Y A1 B1 A2 B2 max IA1 n A2j IB1 n b2 IA1 n B2 B1 n A2 1-1 It is obvious that A1 n A21 k and B1 nB21 k imply Y A1 B1 A2 B2 2k for sets satisfying A1 n B1 A2 n B2 0 therefore the following theorem is really a sharpening of Theorem . Theorem Let IXI n. The family of all q-element subsets of X can be partitioned into disjoint pairs except possibly one if n is