# Saturated $k$-Sperner Systems of Minimum Size

 Importance: Medium ✭✭
 Author(s): Morrison, Natasha Noel, Jonathan A. Scott, Alex
 Subject: Combinatorics » Posets
 Keywords: antichain extremal combinatorics minimum saturation saturation Sperner system
 Posted by: Jon Noel on: April 12th, 2014
Question   Does there exist a constant and a function such that if , then every saturated -Sperner system has cardinality at least ?

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:

Theorem  (Morrison, Noel and Scott (2014))   There exists a constant and a function such that for every and every set such that there exists a saturated -Sperner system in of cardinality at most .

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:

Question  (Morrison, Noel, Scott (2014))   Does there exist a constant and a function such that if and is a saturated antichain in which every element of has cardinality between and , then ?

A more general problem is the following:

Question   Given integers and a set , what is the minimum size of a saturated antichain in in which every set of has cardinality between and ?

## 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.