The Induced Saturation Number for ${\mathcal{V}}_3$ is Linear

Abstract

Given a poset $\mathcal{P}$, a family $\mathcal{F}$ of elements in the Boolean lattice is said to be $\mathcal{P}$-saturated if $\mathcal{F}$ does not contain an induced copy $\mathcal{P}$, but every proper superset of $\mathcal{F}$ contains one. The minimum size of a $\mathcal{P}$-saturated family in the $n$-dimensional Boolean lattice is denoted by $sa{t}^{\ast }(n,\mathcal{P})$.\par In this paper, we consider the poset ${\mathcal{V}}_3$ (the four element poset with one minimal element and three incomparable maximal elements) and show that $sa{t}^{\ast }(n,{\mathcal{V}}_3)\ge \frac{n}{2}$. This represents the first linear lower bound for $sa{t}^{\ast }(n,{\mathcal{V}}_3)$, improving upon the previously best-known bound of $2\sqrt{n}$. Our result establishes that $sa{t}^{\ast }(n,{\mathcal{V}}_3)=\hat{I}˜(n)$.

8 pages, 7 figures. The introduction has been rewritten