A Polynomial Upper Bound for Poset Saturation

Abstract

Given a finite poset $\mathcal{P}$, we say that a family $\mathcal{F}$ of subsets of $[n]$ is $\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 saturation 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 prove that the saturation number for any given poset grows at worst polynomially. More precisely, we show that ${\text{sat}}^{\ast }(n,\mathcal{P})=O(n^c)$, where $c\le |\mathcal{P}{|}^2/4+1$ is a constant depending on $\mathcal{P}$ only. We obtain this result by bounding the VC-dimension of our family.

7 pages, 2 figures