1:30-2:15 PM, Sunday, March 25

Room: SC107 - first floor

Chair: S.S. Ravindran

** 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. Letting P_{k} denote the k-element
chain (path poset), Sperner's Theorem (1928) gives that the largest size of
an antichain of subsets of [n], La(n, P_{2}) =(^{ n}_{⌊n/2⌋})
, and Erd.os (1945) showed more
generally that La(n, P_{k}) is the sum of the k middle binomial coefficients in n. In
recent years Katona and his collaborators investigated La(n, P) for other posets P.
It can be very challenging, even for small posets. Based on results we have, Griggs
and Lu conjecture that π(P) := limit _{n→∞} La(n, P)/(^{ n}_{⌊n/2⌋})
exists for general posets P, and, moreover, it is an integer obtained in a specific way.
For, k≥ 2, let D_{k}
denote the k-diamond poset {A < B1, . . . ,Bk < 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 that π(D_{2}) < 2.273, if it exists. This is a
stubborn open problem, since we expect π(D_{2}) = 2. It is then surprising that, with
appropriate partitions of the set of full chains, we can explicitly determine π(D_{k}) for
infinitely many values of k, and, moreover, describe the extremal D_{k}-free families.
For these fortunate values of k, and for a growing collection of other posets P, we
have that La(n, P) is a sum of middle binomial coefficients in n, while for other
values of k and for most P, it seems that La(n, P) is far more complicated.

**Jerrold Griggs**

Department of Mathematical Sciences

* University of South Carolina, USA *

SEAS2012 Home | Program | Hotel | Location/Maps | Registration |