Induced and non-induced poset saturation problems

[摘要] A subfamily g c C 21n1 of sets is a non-induced (weak) copy of a poset P in F if there exists a bijection i : P c such that p Gp q implies i(p) C i(q). In the case where in addition p Gp q holds if and only if i(p) C i(q), then g is an induced (strong) copy of P in T. We consider the minimum number sat(n, P) [resp. sat* (n, P)] of sets that a family F C 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 E 2[n] \.F creates a non-induced [induced] copy of P. We prove for any finite poset P that sat(n, P) < 21P1-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) < Kp for some constant depending only on P or sat* (n, P) > log2 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. (C) 2021 The Author(s). Published by Elsevier Inc.

[发布日期] 2021-11-01

[关键词] Extremal set theory;Forbidden subposet problem;Saturation problem