# 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
 Recomm. for undergrads: yes
 Posted by: Jon Noel on: April 12th, 2014

\begin{question} Does there exist a constant $c>1/2$ and a function $n_0(k)$ such that if $|X|\geq n_0(k)$, then every saturated $k$-Sperner system $\mathcal{F}\subseteq \mathcal{P}(X)$ has cardinality at least $2^{(1+o(1))ck}$? \end{question}

The \emph{power set} of a set $X$, denoted $\mathcal{P}(X)$, is the collection of all subsets of $X$. A collection $\mathcal{F}\subseteq\mathcal{P}(X)$ is said to be a \emph{$k$-Sperner system} if there does not exist a subcollection $\{A_1,\dots,A_{k+1}\}\subseteq \mathcal{F}$ such that $A_1\subsetneq \dots\subsetneq A_{k+1}$; such a subcollection is called a \emph{$(k+1)$-chain}. A $k$-Sperner system $\mathcal{F}\subseteq\mathcal{P}(X)$ is said to be \emph{saturated} if for every subset $S$ of $X$ not contained in $\mathcal{F}$, the collection $\mathcal{F}\cup\{S\}$ contains a $(k+1)$-chain.

Gerbner et al. [1] proved that if $|X|\geq k$, then every saturated $k$-Sperner System in $\mathcal{P}(X)$ has cardinality at least $2^{k/2-1}$. Moreover, they conjectured that there exists a function $n_0(k)$ such that if $|X|\geq n_0(k)$, then the minimum size of a saturated $k$-Sperner System in $\mathcal{P}(X)$ has size $2^{k-1}$. This was disproved by Morrison, Noel and Scott in [2], who showed the following:

\begin{theorem}[Morrison, Noel and Scott (2014)] There exists a constant $\varepsilon>0$ and a function $n_0(k)$ such that for every $k$ and every set $X$ such that $|X|\geq n_0(k)$ there exists a saturated $k$-Sperner system in $\mathcal{P}(X)$ of cardinality at most $2^{(1-\varepsilon)k}$. \end{theorem}

The value of $\varepsilon$ which can be deduced from their proof is approximately $\left(1-\frac{\log_2(15)}{4}\right)\approx 0.023277$. Moreover, in [2] it was shown that there exists a function $n_0(k)$ and a constant $c\in [1/2,1-\varepsilon]$ such that if $|X|\geq n_0(k)$, then the size of the smallest $k$-Sperner System in $\mathcal{P}(X)$ is asymptotically $2^{(1+o(1))ck}$. The problem stated here is to determine whether $c>1/2$.

A $1$-Sperner system is called an \emph{antichain}. As was observed in [2], a positive answer to the above question would follow from a positive answer to the following question:

\begin{question}[Morrison, Noel, Scott (2014)] Does there exist a constant $c>1/2$ and a function $n_0(k)$ such that if $|X|\geq n_0(k)$ and $\mathcal{A}\subseteq\mathcal{P}(X)$ is a saturated antichain in which every element of $\mathcal{A}$ has cardinality between $\left\lfloor\frac{k}{2}\right\rfloor$ and $|X|-\left\lfloor\frac{k}{2}\right\rfloor +1$, then $|\mathcal{A}|\geq 2^{(1+o(1))ck}$? \end{question}

A more general problem is the following:

\begin{question} Given integers $a,b$ and a set $X$, what is the minimum size of a saturated antichain $\mathcal{A}$ in $\mathcal{P}(X)$ in which every set of $\mathcal{A}$ has cardinality between $a$ and $|X|-b$? \end{question}

## 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.
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "math_score": 0.952781617641449, "perplexity": 283.81371474581044}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.3, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "warc_path": "s3://commoncrawl/crawl-data/CC-MAIN-2017-47/segments/1510934805049.34/warc/CC-MAIN-20171118210145-20171118230145-00476.warc.gz"}