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: Erd˝s-Ko-Rado theorems for uniform set-partition o systems. | Erdos-Ko-Rado theorems for uniform set-partition systems Karen Meagher Department of Mathematics and Statistics University of Ottawa Ottawa Ontario Canada kmeagher@ Lucia Moura School of Information Technology and Engineering University of Ottawa Ottawa Ontario Canada lucia@ Submitted Apr 29 2005 Accepted Jun 21 2005 Published Aug 25 2005 Mathematics Subject Classifications 05D05 Abstract Two set partitions of an n-set are said to t-intersect if they have t classes in common. A k-partition is a set partition with k classes and a k-partition is said to be uniform if every class has the same cardinality c n k. In this paper we prove a higher order generalization of the Erdos-Ko-Rado theorem for systems of pairwise t-intersecting uniform k-partitions of an n-set. We prove that for n large enough any such system contains at most y n-tc n- t 1 c n- k-1 A partitions and k-t c c c this bound is only attained by a trivially t-intersecting system. We also prove that for t 1 the result is valid for all n. We conclude with some conjectures on this and other types of intersecting partition systems. Keywords Erdos-Ko-Rado theorems of higher order intersecting set partitions. 1 Introduction In this paper we prove two Erd os-Ko-Rado type theorems for systems of uniform set partitions. They are stated after some notation and background results are introduced. For i j 2 N i j let i j denote the set i i 1 . j . For k n 2 N set fcO M 1 n A k . A system A of subsets of 1 n is said to be k-uniform if A nO. A set system A nO is said to be t-intersecting if A1 0 A2I t for all A1 A2 2 A. We say that A n is a trivially t-intersecting set system if A is equal up THE ELECTRONIC JOURNAL OF COMBINATORICS 12 2005 R40 1 to permutations on 1 n to A n k t f . n A 2 k 1 t c A The Erdos-Ko-Rado theorem 5 is concerned with the maximal cardinality of k-uniform t-intersecting set systems as well as with the structure of such maximal systems. Theorem EKR 5 Let n k t 1 and .
