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: A note on Kk,k -cross free families. | A note on Kfc fc-cross free families Andrew Suk Courant Institute of Mathematical Sciences New York University New York USA suk@ Submitted Aug 19 2008 Accepted Oct 20 2008 Published Oct 29 2008 Mathematics Subject Classifications 05D05 Abstract We give a short proof that for any fixed integer k the maximum number size of a Kk k-cross free family is linear in the size of the groundset. We also give tight bounds on the maximum size of a Kk-cross free family in the case when F is intersecting or an antichain. Introduction Let F c 2 n . Two sets A B 2 F cross if 1. A B . 2. B c A and A c B. F c 2 n is said to be Kk-cross free if it does not contain k sets A1 . Ak such that Aj cross Aj for every i j. Karzanov and Lomonosov conjectured that for any fixed k the maximum size of a Kk-cross free family F c 2 n is O n 5 1 . The conjecture has been proven for k 2 and k 3 7 4 . For general k the best known upperbound is 2 k 1 n logn which can easily be seen by a double counting argument on the number of sets of a fixed size. We say that F is Kk k-cross free if it does not contain 2k sets A1 . Ak B1 . Bk 2 F such that Aị crosses Bj for all i j. In this paper we prove the following Theorem 1 Let F c 2 ra be a Kk k -cross free family. Then F 2k 1 2n. In this section we give upperbounds on the maximum size of certain classes of Kk-cross free families. By applying Dilworth s Theorem 2 one can obtain a tight bound THE ELECTRONIC JOURNAL OF COMBINATORICS 15 2008 N39 1 for intersecting k-cross free families. Recall a family F c 2 n is intersecting if for every A B 2 F a n B 0. Theorem 2 Let F c 2 n be a family that is k-cross free and intersecting. Then F k 1 n and this bound is asymptotically tight. We also obtain tight bounds for Kk-cross free families that is an antichain. Recall F is an antichain if no set in F is a subset of another. Theorem 3 For k 3 let F c 2 n be a family that is k-cross free and an antichain. Then F k 1 n 2 and this bound is asymptotically tight. .
