Induced and non-induced poset saturation problems

A subfamily $\mathcal G \subseteq \mathcal F \subseteq 2^{[n]}$ of sets is a non-induced (weak) copy of a poset $P$ in $\mathcal F$ if there exists a bijection $i:P \to \mathcal G$ such that $p\le_P q$ implies $i(p)\subseteq i(q)$. In the case where in addition$p\le_P q$ holds if and only if $i(p)\subseteq i(q)$, then $\mathcal G$ is an induced (strong) copy of $P$ in $\mathcal F$. We consider the minimum number $sat (n, P)$ [resp. $sat^*(n, P)$] of sets that a family $\mathcal F \subseteq 2^{[n]}$ can have without containing a non-induced [induced] copy of $P$ and being maximal with respect to this property, i.e., the addition of any $G \in 2^{[n]} \setminus \mathcal F$ creates a non-induced [induced] copy of $P$.

We prove for any finite poset $P$ that $sat(n, P)\le 2^{|P|-2}$, a bound independent of the size $n$ of the ground set. For induced copies of $P$, there is a dichotomy: for any poset $P$ either $sat^*(n,P)\le K_P$ for some constant depending only on $P$ or $sat^*(n,P)\ge \log_2 n$. We classify several posets according to this dichotomy, and also show better upper and lower bounds on $sat(n,P)$ and $sat^*(n,P)$ for specific classes of posets.

Our main new tool is a special ordering of the sets based on the colexicographic order. It turns out that if $P$ is given, processing the sets in this order and adding the sets greedily into our family whenever this does not ruin non-induced [induced] $P$-freeness, we tend to get a small size non-induced [induced] $P$-saturating family.

Joint work with Keszegh, Lemons, Martin, and Pálvölgyi.