On Saturated k-Sperner Systems
On Saturated k-Sperner Systems
复制标题
饱和 k-Sperner 系统
DOI：
10.37236/4136
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
A. Scott
中科院分区：
文献类型：
--
作者：
Natasha Morrison;Jonathan A. Noel;A. Scott
给定一个$ x $，一个集合$ \ mathcal {f} \ subseteq \ mathcal {p}（x）$，如果不包含长度$ k+1 $的链设置包含，如果相对于此属性是最大的，则将其饱和。 Gerbner等。推测，如果$ | x | $相对于$ k $，则饱和$ k $ -sperner系统的最小大小$ 2^{k-1} $。我们通过证明存在$ \ varepsilon> 0 $来反驳这一猜想，以便每$ k $和$ | x | \ geq n_0（k）$存在饱和的$ k $ -sperner系统$ \ mathcal {f} \ subseteq \ subseteq \ mathcal {p}（x）$，具有$ 2^{（1- \ varepsilon）k} k} $ at tak in cal 。一个集合$ \ Mathcal {f} \ subseteq \ Mathcal {p}（x）$被认为是一个过饱和的$ k $ -sperner系统，如果每个$ s \ in \ mathcal {p}（x）（x） Mathcal {F} $，$ \ Mathcal {F} \ Cup \ {S \} $包含更多链条长度$ k+1 $，大于$ \ Mathcal {f} $。 Gerbner等。证明，如果$ | x | \ geq k $，那么最小的集合包含$ 2^{k/2-1} $和$ o \ left（\ frac {\ log {k}}} {k} {k} 2^ k \ right）$元素。我们表明，如果$ | x | \ geq k^2+k $，那么下限是最好的，最多可达多项式因素。
Given a set $X$, a collection $\mathcal{F}\subseteq\mathcal{P}(X)$ is said to be $k$ -Sperner if it does not contain a chain of length $k+1$ under set inclusion and it is saturated if it is maximal with respect to this property. Gerbner et al. conjectured that, if $|X|$ is sufficiently large with respect to $k$, then the minimum size of a saturated $k$-Sperner system $\mathcal{F}\subseteq\mathcal{P}(X)$ is $2^{k-1}$. We disprove this conjecture by showing that there exists $\varepsilon>0$ such that for every $k$ and $|X| \geq n_0(k)$ there exists a saturated $k$-Sperner system $\mathcal{F}\subseteq\mathcal{P}(X)$ with cardinality at most $2^{(1-\varepsilon)k}$. A collection $\mathcal{F}\subseteq \mathcal{P}(X)$ is said to be an oversaturated $k$ -Sperner system if, for every $S\in\mathcal{P}(X)\setminus\mathcal{F}$, $\mathcal{F}\cup\{S\}$ contains more chains of length $k+1$ than $\mathcal{F}$. Gerbner et al. proved that, if $|X|\geq k$, then the smallest such collection contains between $2^{k/2-1}$ and $O\left(\frac{\log{k}}{k}2^k\right)$ elements. We show that if $|X|\geq k^2+k$, then the lower bound is best possible, up to a polynomial factor.