tailieunhanh - Báo cáo toán học: "Flattening Antichains with Respect to the Volume"

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: Flattening Antichains with Respect to the Volume. | Flattening Antichains with Respect to the Volume Ljiljana Brankovic Department of Computer Science and Software Engineering The University of Newcastle NSW 2308 Australia e-mail lbrankov@ . Paulette Lieby School of Mathematical and Physical Sciences Northern Territory University Darwin NT Australia e-mail paule@ Mirka Miller Department of Computer Science and Software Engineering The University of Newcastle NSW 2308 Australia e-mail mirka@ . Submitted September 10 1998 Accepted November 9 1998. AMS Subject Classification 05D99. Abstract We say that an antichain A in the boolean lattice Bn is flat if there exists an integer k 0 such that every set in A has cardinality either k or k 1. Define the volume of A to be 52AeA l . We prove that for every antichain A in Bn there exist an antichain which is flat and has the same volume as A. THE ELECTRONIC .JOURNAL OF COMBINATORICS 6 1999 R1 2 1 Introduction Throughout the paper the universal set is n 1 2 . ng. A collection A of subsets of n is an antichain if for any distinct A B 2 A A c B. The parameters of an antichain A are the non-negative integers pi 0 i n such that pi Ai where Ai A A i A 2 Ag. Let A be an antichain. We say that A is flat if for any A 2 A A k or A k 1 for some non-negative integer k. Thus the parameters of A are such that pi 0 for i k k 1. The size of A is A and its volume is V A XAeA A . The concept of attening an antichain is illustrated in the proof of Sperner s seminal result which establishes the maximal size an antichain can have. In this proof it is shown that if A is an antichain of size s then there exists an antichain consisting of s _ _ -sets. A result by Kleitman and Milner 5 Clements 2 and more recently by Maire 8 shows that if A is an antichain whose average set size is an integer then there exists a flat antichain having the same size and volume as A. The ideal of a collection of sets B is IB C C c B B 2 Bg. Clements 2 proved that given s .