|国家预印本平台
首页|Gluing Posets and the Dichotomy of Poset Saturation Numbers

Gluing Posets and the Dichotomy of Poset Saturation Numbers

Gluing Posets and the Dichotomy of Poset Saturation Numbers

来源:Arxiv_logoArxiv
英文摘要

Given a finite poset $\mathcal P$, we say that a family $\mathcal F$ of subsets of $[n]$ is $\mathcal P$-saturated if $\mathcal F$ does not contain an induced copy of $\mathcal P$, but adding any other set to $\mathcal F$ creates an induced copy of $\mathcal P$. The induced saturation number of $\mathcal P$, denoted by $\text{sat}^*(n,\mathcal P)$, is the size of the smallest $\mathcal P$-saturated family with ground set $[n]$. The saturation number for posets is known to exhibit a dichotomy: it is either bounded or it has at least $\sqrt n$ rate of growth. Whether or not a poset has bounded or unbounded saturation number is not a monotone property, in the sense that if a poset is present as an induced copy in another poset, their saturation numbers are generally unrelated. Moreover, so far there is no characterization for posets that have unbounded saturation number. Let $\mathcal P_1$ and $\mathcal P_2$ be two finite posets. We denote by $\mathcal P_2*\mathcal P_1$ the poset obtained by making all elements of $\mathcal P_1$ strictly less than all elements of $\mathcal P_2$. In this paper we show that this `gluing' operation preserves (under some assumptions) both the bounded and the unbounded saturation number. More precisely, we show that, under minor assumptions, if one of the posets has unbounded saturation number, so does $\mathcal P_2*\mathcal P_1$, but if they both have bounded saturation number, then so does $\mathcal P_2*\mathcal P_1$. We also give linear upper bounds for all complete multipartite posets (which do not have two trivial consecutive layers). We also consider poset percolating families, the poset equivalent of weak saturation for graphs. We determine the exact value for the size of a minimal percolating family, for all posets.

Sean Jaffe、Maria-Romina Ivan

数学

Sean Jaffe,Maria-Romina Ivan.Gluing Posets and the Dichotomy of Poset Saturation Numbers[EB/OL].(2025-03-15)[2025-05-14].https://arxiv.org/abs/2503.12223.点此复制

评论