Exact antichain saturation numbers via a generalisation of a result of Lehman-Ron
Exact antichain saturation numbers via a generalisation of a result of Lehman-Ron
复制标题
通过 Lehman-Ron 结果的概括得到精确的反链饱和数
DOI：
10.5817/cz.muni.eurocomb23-017
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Tom Johnston
中科院分区：
文献类型：
--
作者：
P. Bastide;C. Groenland;Hugo Jacob;Tom Johnston
对于给定的正整数$k$和$n$，$\{1，\dots，n\}$的子集的族$\mathcal{F}$是$k$-反链饱和的，如果它不包含大小为$k$的反链，但是将任何集合添加到$\mathcal{F}$会创建大小为$k$的反链。我们使用sat$^*（n，k）$来表示这样的族的最小尺寸。对于所有的k和足够大的n，我们确定sat ^*（n，k）的精确值。我们的结果意味着sat ^*（n，k）=n（k-1）-\Theta（k\log k）$，这证实了反链饱和的几个推论.在此之前，sat$^*（n，k）$的精确值只在k$到6 $的范围内是已知的。我们还证明了Lehman-Ron的一个结果的加强，这可能是独立的利益。我们表明，给定布尔格中的$m$不相交链，我们可以创建覆盖相同元素的$m$不相交无跳链（如果任何两个连续元素的大小相差恰好一个，则称为无跳链）。论文的完整版本可以在这里找到\cite{antichainsaturation}。
For given positive integers $k$ and $n$, a family $\mathcal{F}$ of subsets of $\{1,\dots,n\}$ is $k$-antichain saturated if it does not contain an antichain of size $k$, but adding any set to $\mathcal{F}$ creates an antichain of size $k$. We use sat$^*(n, k)$ to denote the smallest size of such a family. For all $k$ and sufficiently large $n$, we determine the exact value of sat$^*(n, k)$. Our result implies that sat$^*(n, k)=n(k-1)-\Theta(k\log k)$, which confirms several conjectures on antichain saturation. Previously, exact values for sat$^*(n,k)$ were only known for $k$ up to $6$. We also prove a strengthening of a result of Lehman-Ron which may be of independent interest. We show that given $m$ disjoint chains in the Boolean lattice, we can create $m$ disjoint skipless chains that cover the same elements (where we call a chain skipless if any two consecutive elements differ in size by exactly one). The complete version of the paper can be found here \cite{antichainsaturation}.
最小钻石饱和家庭
DOI：
10.37256/cm.3220221333
发表时间：
2022
期刊：
Contemporary Mathematics
影响因子：
--
作者：
Ivan M
通讯作者：
Ivan M