IMI Interdisciplinary Mathematics InstituteCollege of Arts and Sciences

Searching for Diamonds

  • April 2, 2012
  • 3:50 p.m.
  • LeConte 312

Abstract

We describe joint work with Wei-Tian Li and Lincoln Lu, surveying problems of the following form: Given a finite poset ( P ), we consider the largest size ( \text{La}(n,P) ) of a family of subsets of ( [n]:={1,...,n} ) that contains no (weak) subposet P. Classical results of Sperner and Erdos solve the problem for ( P ) being a ( k )-element chain. In recent years Katona and his collaborators investigated the problem for other posets ( P ), finding that it can be very challenging, even for small posets.

For ( k ) at least 2, let ( D_k ) denote the ( k )-diamond poset of elements ( A < B_1 , \ldots , B_k < C ). For ( D_2 ), even the asymptotic behavior of ( \text{La}(n,P) ) remains open (though we believe it should be asymptotic to twice the middle binomial coefficient in ( n ) ). 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 derive a good upper bound on ( \text{La}(n,P) ) (which we learned in a recent seminar has been improved by Martin et al.) It is then surprising that, with appropriate partitions of the set of full chains, we can explicitly determine ( \text{La}(n,D_k) ) for all ( n ), for infinitely many values of ( k ). We survey the growing list of such posets ( P ) that can be solved. We describe a related open problem of Kleitman's on union-free families of subsets, and pay tribute to Katona in honor of his 70th birthday (plus one).

© Interdisciplinary Mathematics Institute | The University of South Carolina Board of Trustees | Webmaster
USC