Induced and non-induced poset saturation problems.

A subfamily G ⊆ F ⊆ 2 [ n ] of sets is a non-induced (weak) copy of a poset P in F if there exists a bijection i : P → G such that p ≤ P q implies i (p) ⊆ i (q). In the case where in addition p ≤ P q holds if and only if i (p) ⊆ i (q) , then G is an induced (strong) copy of P in F. We consider the minimum number sat (n , P) [resp. sat ⁎ (n , P) ] of sets that a family F ⊆ 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 ∈ 2 [ n ] ∖ F creates a non-induced [induced] copy of P. We prove for any finite poset P that sat (n , P) ≤ 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) ≤ K P for some constant depending only on P or sat ⁎ (n , P) ≥ 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. [ABSTRACT FROM AUTHOR]