Induced saturation for complete bipartite posets

Abstract

Given $s,t\in \mathbb{N}$, a complete bipartite poset ${\mathcal{K}}_{s,t}$ is a poset whose Hasse diagram consists of $s$ pairwise incomparable vertices in the upper layer and $t$ pairwise incomparable vertices in the lower layer, such that every vertex in the upper layer is larger than all vertices in the lower layer. A family $\mathcal{F}\subseteq 2^{[n]}$ is called induced ${\mathcal{K}}_{s,t}$-saturated if $(\mathcal{F},\subseteq )$ contains no induced copy of ${\mathcal{K}}_{s,t}$, whereas adding any set from $2^{[n]}\backslash \mathcal{F}$ to $\mathcal{F}$ creates an induced ${\mathcal{K}}_{s,t}$. Let ${\mathrm{sat}}^{\ast }(n,{\mathcal{K}}_{s,t})$ denote the smallest size of an induced ${\mathcal{K}}_{s,t}$-saturated family $\mathcal{F}\subseteq 2^{[n]}$. It was conjectured that ${\mathrm{sat}}^{\ast }(n,{\mathcal{K}}_{s,t})$ is superlinear in $n$ for certain values of $s$ and $t$. In this paper, we show that ${\mathrm{sat}}^{\ast }(n,{\mathcal{K}}_{s,t})=O(n)$ for all fixed $s,t\in \mathbb{N}$. Moreover, we prove a linear lower bound on ${\mathrm{sat}}^{\ast }(n,\mathcal{P})$ for a large class of posets $\mathcal{P}$, particularly for ${\mathcal{K}}_{s,2}$ with $s\in \mathbb{N}$.

arXiv comment10 pages, 9 figures, minor typos corrected