IMI Interdisciplinary Mathematics InstituteCollege of Arts and Sciences

Poset-free Families of Subsets

  • Sept. 29, 2017
  • 2:30 p.m.
  • LeConte 317R

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 earlier results we conjectured with Lu (2008) 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. The conjecture has been verified for various families of posets. For most k at least 2, our work with Li verifies the conjecture for D_k, which is the k-diamond poset {A<B_1,...,B_k < C}. Yet, the case k=2 remains open, after considerable effort by researchers. We expect pi(D_2)=2, the easy lower bound. Recently, Grosz, Methuku, and Tompkins brought the upper bound down below 2.21. Tools used on these problems include probabilistic reasoning, such as bounding the average number of times a random full chain meets a P-free family F, called the Lubell function of F.

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