Abstract
Given a finite poset P, we consider the largest size
La(n,P) of a family of subsets of [n]:={1,...,n} that
contains no (weak) subposet P. Early theorems of Sperner
and Katona solve this problem when P is the k-element chain
(path poset) P_k, where it is the sum of the middle k-1
binomial coefficients in n.
Katona and his collaborators investigated La(n,P)
for other posets P. It can be very challenging, even for small posets.
Based on results to date, G. and Lu (2008) conjecture that
pi(P), which is the limit as n goes to infinity, of
La(n,P)/{n\choose{n/2}}, exists for general posets P.
Moreover, it is an integer obtained in a specific way.
For k at least 2 let D_k denote the k-diamond poset
{A< B_1,...,B_k < C}. Using probabilistic reasoning
to bound the average number of
times a random full chain meets a P-free family F,
called the Lubell function of F, we prove with Li and Lu that
pi(D_2)<2.273, if it exists. This is a stubborn open problem,
since we expect pi(D_2)=2. Kramer, Martin, and Young have the
current best bound, 2.25. It is then surprising that, with
appropriate partitions of the set of full chains, we can
explicitly determine pi(D_k) for infinitely many values of k,
and, moreover, describe the extremal D_k-free families.
With Li we develop a theory of poset properties that verifies the
conjecture for many more posets, though for most P, it seems
that La(n,P) is far more complicated.