A polynomial upper bound for poset saturation

Journal article

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 $\mathrm{sat}^*(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 $\mathrm{sat}^*(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.

Authors: Bastide, P; Groenland, C; Ivan, M-R; Johnston, T

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Elsevier
• Journal: European Journal of Combinatorics
• Volume: 129
• Article number: 103970
• Publication date: 2024-05-14
• DOI: 10.1016/j.ejc.2024.103970
• EISSN: 1095-9971
• ISSN: 0195-6698
• Language: English