Set families with forbidden subposets

Abstract

Let $F$ be a family of subsets of $\{1,\dots ,n\}$. We say that $F$ is $P$-free if the inclusion order on $F$ does not contain $P$ as an induced subposet. The \emph{Turán function} of $P$, denoted ${\pi }^{\ast }(n,P)$, is the maximum size of a $P$-free family of subsets of $\{1,\dots ,n\}$. We show that ${\pi }^{\ast }(n,P)\le (4r+O(\sqrt{r}))\left(\genfrac{}{}{0ex}{}{n}{n/2}\right)$ if $P$ is an $r$-element poset of height at most $2$. We also show that ${\pi }^{\ast }(n,S_r)=(r+O(\sqrt{r}))\left(\genfrac{}{}{0ex}{}{n}{n/2}\right)$ where $S_r$ is the standard example on $2r$ elements, and that ${\pi }^{\ast }(n,B_2)\le (2.583+o(1))\left(\genfrac{}{}{0ex}{}{n}{n/2}\right)$, where $B_2$ is the $2$-dimensional Boolean lattice.

16 pages, 1 figure

Cited by in corpus (1)

• Lubell mass and induced partially ordered sets