Saturation for the Butterfly Poset

Abstract

Given a finite poset $\mathcal{P}$, we call a family $\mathcal{F}$ of subsets of $[n]$ $\mathcal{P}$-saturated if $\mathcal{F}$ does not contain an induced copy of $\mathcal{P}$, but adding any other set to $\mathcal{F}$ creates an induced copy of $\mathcal{P}$. The induced saturated number of $\mathcal{P}$, denoted by ${\text{sat}}^{\ast }(n,\mathcal{P})$, is the size of the smallest $\mathcal{P}$-saturated family with ground set $[n]$. In this paper we are mainly interested in the four-point poset called the butterfly. Ferrara, Kay, Kramer, Martin, Reiniger, Smith and Sullivan showed that the saturation number for the butterfly lies between ${\log }_{2}n$ and $n^2$. We give a linear lower bound of $n+1$. We also prove some other results about the butterfly and the poset $\mathcal{N}$.

13 pages