TAILIEUCHUNG - Báo cáo toán học: "Set families with a forbidden subposet"

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: Set families with a forbidden subposet. | Set families with a forbidden subposet Boris Bukh Department of Pure Mathematics and Mathematical Statistics Cambridge CB3 0WA UK and Churchill College Cambridge CB3 0DS UK Submitted Dec 14 2008 Accepted Nov 4 2009 Published Nov 30 2009 Mathematics Subject Classification 06A07 05D05 Abstract We asymptotically determine the size of the largest family F of subsets of 1 . n not containing a given poset P if the Hasse diagram of P is a tree. This is a qualitative generalization of several known results including Sperner s theorem. Introduction We say that a poset P is a subposet of a poset P if there is an injective map f P P such that a p b implies f a p f b . A poset P is an induced subposet of P if there is an injective map f P P for which a Cp b if and only if f a CP f b . For instance A is a subposet of ị but not an induced subposet. For a poset P a Hasse diagram denoted by H P is a graph whose vertices are elements of P and xy is an edge if x y and for no other element z of P we have x z y. Let n 1 . n and denote by 2 n the collection of all subsets of n . One can think of a family F of subsets of n as a poset under inclusion. In this way F becomes an induced subposet of the Boolean lattice. In this paper we examine the size of the largest family F c 2 n subject to the condition that F does not contain a fixed finite subposet P . We do not require P to be an induced subposet. A set family F not containing a subposet P will be called a P-free family. We denote by ex P n the size of the largest P-free family F c 2 n . For example the classical Sperner s theorem Spe28 asserts that ex l n Ln 2j - This work was done while the author studied at Princeton University. Its intellectual and financial support are gratefully acknowledged. THE ELECTRONIC JOURNAL OF COMBINATORICS 16 2009 R142 1 Erdos Erd45 extended Sperner s result and proved that if Cl denotes the chain of length l then ex Cl n is equal to the sum of l 1 largest binomial coefficients of

TÀI LIỆU LIÊN QUAN
TỪ KHÓA LIÊN QUAN
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.