IMI Interdisciplinary Mathematics InstituteCollege of Arts and Sciences

Set Families with a Forbidden Induced Subposet

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

Abstract

The classic Sperner's theorem asserts that the largest family of subsets of $\{1,...,n\}$ where no member contains another member has size ${n\choose n/2}$. This can be viewed as the first major result toward the more general problem of determining $La(n,H)$, defined to be the largest size of a subfamily of the Boolean lattice $B _ n$ that does not contain a given poset $H$ as a subposet. A related and more difficult problem is to determine $La^ * (n,H)$, defined to be the largest size of a subfamily of $B _ n$ that excludes $H$ as an induced subposet.

Many results were obtained in recent years on $La(n,H)$, the most impressive of which is the result by Boris Bukh that says if $H$ is any poset whose Hasse diagram is a tree of height $k$, then $La(n,H) = (k-1+o(1)){n\choose n/2}$.

We strengthen Bukh's result by establishing the induced version of his theorem. We prove that for any poset $H$ whose Hasse diagram is a tree of height $k$, we have $La^ * (n,H)=(k-1+o(1)){n\choose n/2}$.

This is joint work with Tao Jiang of Miami University.

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