Poset-free families and Lubell-boundedness

JOURNAL OF COMBINATORIAL THEORY SERIES A

卷:134

Article

Griggs, Jerrold R.¹  Li, Wei-Tian² 

[1] Univ S Carolina, Dept Math, Columbia, SC 29208 USA

[2] Natl Chung Hsing Univ, Dept Appl Math, Taichung 40227, Taiwan

关键词: Poset-free family;    Boolean lattice;    Extremal problems for subsets;    Sperner Theory;    Lubell function;   

DOI  :  10.1016/j.jcta.2015.03.010

来源: Elsevier

【 摘 要 】

Given a finite poset P, we consider the largest size La(n,P) of a family F of subsets of [n] := {1,...,n} that contains no subposet P. This continues the study of the asymptotic growth of La(n,P); it has been conjectured that for all P, pi(P) := lim(n ->infinity) La(n,P)/ [GRAPHICS] exists and equals a certain integer, e(P). This is known to be true for paths, and for several more general families of posets, while for the simple diamond poset D-2, even the existence of pi frustratingly remains open. Here we develop theory to show that pi(P) exists and equals the conjectured value e(P) for many new posets P. We introduce a hierarchy of properties for posets, each of which implies pi = e, and some implying more precise information about La(n,P). The properties relate to the Lubell function of a family F of subsets, which is the average number of times a random full chain meets F. We present an array of examples and constructions that possess the properties. (C) 2015 Elsevier Inc. All rights reserved.

【 授权许可】

Free