Poset-free Families of Subset

Thursday, November 6, 2014 - 2:00pm - 3:00pm
Lind 305
Jerrold Griggs (University of South Carolina)
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

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

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.