Minimal Diamond-Saturated Families

Abstract

For a given fixed poset $\mathcal{P}$ we say that a family of subsets of $[n]$ is $\mathcal{P}$-saturated if it does not contain an induced copy of $\mathcal{P}$, but whenever we add to it a new set, an induced copy of $\mathcal{P}$ is formed. The size of the smallest such family is denoted by ${\text{sat}}^{\ast }(n,\mathcal{P})$. For the diamond poset ${\mathcal{D}}_2$ (the two-dimensional Boolean lattice), Martin, Smith and Walker proved that $\sqrt{n}\le {\text{sat}}^{\ast }(n,{\mathcal{D}}_2)\le n+1$. In this paper we prove that ${\text{sat}}^{\ast }(n,{\mathcal{D}}_2)\ge (4-o(1))\sqrt{n}$. We also explore the properties that a diamond-saturated family of size $c\sqrt{n}$, for a constant $c$, would have to have.

A short answer to Question 5 has been added, which implies a better multiplicative constant; 8 pages, 6 figures

References in corpus (1)

• Induced and non-induced poset saturation problems

Cited by in corpus (3)

• A Polynomial Upper Bound for Poset Saturation
• The Saturation Number for the Diamond is Linear
• Gluing Posets and the Dichotomy of Poset Saturation Numbers