论文标题
诱导和非诱导的POSET饱和问题
Induced and non-induced poset saturation problems
论文作者
论文摘要
集合$ \ MATHCAL {G} \ subseteq \ Mathcal {f} \ subseteq 2^{[n]} $的$ poset $ p $ in $ \ mathcal {f} $ in Mathcal {f} $是$ i： Q $暗示$ i（p）\ subseteq i（q）$。在此外，如果$ p \ le_p q $在且仅当$ i（p）\ subseteq i（q）$时保持时，则$ \ mathcal {g} $是诱导的（强）$ p $ in $ \ mathcal {f} $。我们认为最低数字$ sat（n，p）$ [resp. \ $ sat^*（n，p）$]的一组，即一个家庭$ \ mathcal {f} \ subseteq 2^{[n]} $可以不包含非诱导的[引起的[$ p $''的副本，并且是该物业的最大范围，i.e.e.e.e.e。 2^{[n]} \ setMinus \ Mathcal {f} $创建了$ p $的非诱导[诱导]副本。 我们证明，对于任何有限的poset $ p $，$ sat（n，p）\ le 2^{| p | -2} $，独立于地面套件的$ n $的绑定。对于$ p $的诱导副本，有一个二分法：对于任何Poset $ p $ $ sat^*（n，p）\ le k_p $，对于某些常数，仅取决于$ p $或$ sat^*（n，n，p）\ ge \ ge \ log_2 n $。我们根据此二分法对几个POSET进行了分类，并在$ SAT（N，P）$和$ SAT^*（n，p）$上显示出更好的上和下限，用于特定的POSET类别。 我们的主要新工具是基于外生物学顺序的特殊订购。事实证明，如果给出了$ p $，按照此顺序处理套件，并在不破坏非引起的[诱导] $ p $ foreness时，将套装添加到我们的家庭中，我们倾向于获得一个小规模的[诱导的] $ p $ pu $饱和的家庭。
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\rightarrow \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.
