Set Families with a Forbidden Subposet

Boris Bukh

Abstract


We asymptotically determine the size of the largest family $\cal F$ of subsets of $\{1,\dots,n\}$ not containing a given poset $P$ if the Hasse diagram of $P$ is a tree. This is a qualitative generalization of several known results including Sperner's theorem.


Full Text: PDF