IP4 Searching for Diamonds

1:30-2:15 PM, Sunday, March 25
Room: SC107 - first floor
Chair: S.S. Ravindran

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 Pk 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, P2) =( n⌊n/2⌋) , and Erd.os (1945) showed more generally that La(n, Pk) 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 Dk 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 π(D2) < 2.273, if it exists. This is a stubborn open problem, since we expect π(D2) = 2. It is then surprising that, with appropriate partitions of the set of full chains, we can explicitly determine π(Dk) for infinitely many values of k, and, moreover, describe the extremal Dk-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

Corrections? Email ravinds@uah.edu.