Induced and non-induced poset saturation problems

Balázs Keszegh; Nathan Lemons; Ryan R. Martin; Dömötör Pálvölgyi; Balázs Patkós

doi:10.1016/j.jcta.2021.105497

paper

Induced and non-induced poset saturation problems

arXiv:2003.04282 · doi:10.1016/j.jcta.2021.105497

Abstract

A subfamily $G \subseteq F \subseteq 2^{[n]}$ of sets is a non-induced (weak) copy of a poset $P$ in $F$ if there exists a bijection $i : P \to G$ such that $p \leq_{P} q$ implies $i (p) \subseteq i (q)$ . In the case where in addition $p \leq_{P} q$ holds if and only if $i (p) \subseteq i (q)$ , then $G$ is an induced (strong) copy of $P$ in $F$ . We consider the minimum number $s a t (n, P)$ [resp.\ $s a t^{*} (n, P)$ ] of sets that a family $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]} ∖ F$ creates a non-induced [induced] copy of $P$ . We prove for any finite poset $P$ that $s a t (n, P) \leq 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 $s a t^{*} (n, P) \leq K_{P}$ for some constant depending only on $P$ or $s a t^{*} (n, P) \geq lo g_{2} n$ . We classify several posets according to this dichotomy, and also show better upper and lower bounds on $s a t (n, P)$ and $s a t^{*} (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.

Added appendix to v3 from v1, as it was accidentally missing from v2

References in corpus (1)

Saturation for the Butterfly Poset

Induced and non-induced poset saturation problems

Abstract

References in corpus (1)

Cited by in corpus (9)