کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4655121 1632938 2015 22 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Poset-free families and Lubell-boundedness
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Poset-free families and Lubell-boundedness
چکیده انگلیسی

Given a finite poset P  , we consider the largest size La(n,P)La(n,P) of a family FF of subsets of [n]:={1,…,n}[n]:={1,…,n} that contains no subposet P  . This continues the study of the asymptotic growth of La(n,P)La(n,P); it has been conjectured that for all P  , π(P):=limn→∞⁡La(n,P)/(n⌊n2⌋) exists and equals a certain integer, e(P)e(P). This is known to be true for paths, and for several more general families of posets, while for the simple diamond poset D2D2, even the existence of π   frustratingly remains open. Here we develop theory to show that π(P)π(P) exists and equals the conjectured value e(P)e(P) for many new posets P  . We introduce a hierarchy of properties for posets, each of which implies π=eπ=e, and some implying more precise information about La(n,P)La(n,P). The properties relate to the Lubell function of a family FF of subsets, which is the average number of times a random full chain meets FF. We present an array of examples and constructions that possess the properties.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Combinatorial Theory, Series A - Volume 134, August 2015, Pages 166–187
نویسندگان
, ,