The Saturation Number for the Diamond is Linear

Abstract

For a fixed poset $\mathcal{P}$ we say that a family $\mathcal{F}\subseteq \mathcal{P}([n])$ is $\mathcal{P}$-saturated if it does not contain an induced copy of $\mathcal{P}$, but whenever we add a new set to $\mathcal{F}$, we form an induced copy of $\mathcal{P}$. The size of the smallest such family is denoted by ${\text{sat}}^{\ast }(n,\mathcal{P})$.\par For the diamond poset ${\mathcal{D}}_2$ (the two-dimensional Boolean lattice), while it is easy to see that the saturation number is at most $n+1$, the best known lower bound has stayed at $O(\sqrt{n})$ since the introduction of the area of poset saturation. In this paper we prove that ${\text{sat}}^{\ast }(n,{\mathcal{D}}_2)\ge \frac{n+1}{5}$, establishing that the saturation number for the diamond is linear. The proof uses a result about certain pairs of set systems.

14 pages, 12 figures