![](/files/happy5.png)
Saturated $k$-Sperner Systems of Minimum Size
![$ c>1/2 $](/files/tex/71b371b57345af0cbcfd2ffd78362b8988723a7d.png)
![$ n_0(k) $](/files/tex/77717a7ba8441af96e47411a5b9a5d4a913f3dba.png)
![$ |X|\geq n_0(k) $](/files/tex/e6c6b51d4e2df6fd85840bc289e38c981674e057.png)
![$ k $](/files/tex/c450c3185f7285cfa0b88d3a903c54f7df601201.png)
![$ \mathcal{F}\subseteq \mathcal{P}(X) $](/files/tex/cb32025ab3209d1516fd6ea63a4d8eb206a81411.png)
![$ 2^{(1+o(1))ck} $](/files/tex/1564812bc34ed3ebd060debb561be85acfb45f10.png)
The power set of a set , denoted
, is the collection of all subsets of
. A collection
is said to be a
-Sperner system if there does not exist a subcollection
such that
; such a subcollection is called a
-chain. A
-Sperner system
is said to be saturated if for every subset
of
not contained in
, the collection
contains a
-chain.
Gerbner et al. [1] proved that if , then every saturated
-Sperner System in
has cardinality at least
. Moreover, they conjectured that there exists a function
such that if
, then the minimum size of a saturated
-Sperner System in
has size
. This was disproved by Morrison, Noel and Scott in [2], who showed the following:
![$ \varepsilon>0 $](/files/tex/d572eb4a7102086da01f1eaefee455fa2bce9456.png)
![$ n_0(k) $](/files/tex/77717a7ba8441af96e47411a5b9a5d4a913f3dba.png)
![$ k $](/files/tex/c450c3185f7285cfa0b88d3a903c54f7df601201.png)
![$ X $](/files/tex/302cdeba125e821f3406302c9789229d48f42ea7.png)
![$ |X|\geq n_0(k) $](/files/tex/e6c6b51d4e2df6fd85840bc289e38c981674e057.png)
![$ k $](/files/tex/c450c3185f7285cfa0b88d3a903c54f7df601201.png)
![$ \mathcal{P}(X) $](/files/tex/059749d0ac29072c18d489b9cd2948d56890b678.png)
![$ 2^{(1-\varepsilon)k} $](/files/tex/25c5801353523ce15df0c24a0b471137e7c73a1b.png)
The value of which can be deduced from their proof is approximately
. Moreover, in [2] it was shown that there exists a function
and a constant
such that if
, then the size of the smallest
-Sperner System in
is asymptotically
. The problem stated here is to determine whether
.
A -Sperner system is called an antichain. As was observed in [2], a positive answer to the above question would follow from a positive answer to the following question:
![$ c>1/2 $](/files/tex/71b371b57345af0cbcfd2ffd78362b8988723a7d.png)
![$ n_0(k) $](/files/tex/77717a7ba8441af96e47411a5b9a5d4a913f3dba.png)
![$ |X|\geq n_0(k) $](/files/tex/e6c6b51d4e2df6fd85840bc289e38c981674e057.png)
![$ \mathcal{A}\subseteq\mathcal{P}(X) $](/files/tex/1b0dab987641056b6710ff1fc603777589b217d4.png)
![$ \mathcal{A} $](/files/tex/3abde4ab7e21fe6fad91d0a03ad306c2c82659d9.png)
![$ \left\lfloor\frac{k}{2}\right\rfloor $](/files/tex/bb80a84bc0b25f7350cd1c697bc12b111f4b7950.png)
![$ |X|-\left\lfloor\frac{k}{2}\right\rfloor +1 $](/files/tex/8804f40b6d06b30644ad2b12c8637c78183c662a.png)
![$ |\mathcal{A}|\geq 2^{(1+o(1))ck} $](/files/tex/5ee2a7914b4c8c550212dbf06310fadbd06c2d4f.png)
A more general problem is the following:
![$ a,b $](/files/tex/64da95924369e81372c4b004946b26a170ee14d2.png)
![$ X $](/files/tex/302cdeba125e821f3406302c9789229d48f42ea7.png)
![$ \mathcal{A} $](/files/tex/3abde4ab7e21fe6fad91d0a03ad306c2c82659d9.png)
![$ \mathcal{P}(X) $](/files/tex/059749d0ac29072c18d489b9cd2948d56890b678.png)
![$ \mathcal{A} $](/files/tex/3abde4ab7e21fe6fad91d0a03ad306c2c82659d9.png)
![$ a $](/files/tex/b1d91efbd5571a84788303f1137fb33fe82c43e2.png)
![$ |X|-b $](/files/tex/a05e1e975eb6deb239ed2ebb517a667f7ff233a2.png)
Bibliography
[1] D. Gerbner, B. Keszegh, N. Lemons, C. Palmer, D. Palvolgyi, and B. Patkos, Saturating Sperner Families, Graphs Combin. 29 (2013), no. 5, 1355–1364. arXiv:1105.4453
*[2] N. Morrison, J. A. Noel, A. Scott. On Saturated k-Sperner Systems. arXiv:1402.5646 (2014). arXiv:1402.5646
* indicates original appearance(s) of problem.