Saturated $k$-Sperner Systems of Minimum Size

Saturated $k$-Sperner Systems of Minimum Size

Definitions and mathematical statement

For a finite set $X$, write $2^X$ for its power set. A family $\mathcal F\subseteq2^X$ is $k$-Sperner if it contains no strict chain $A_0\subsetneq A_1\subsetneq\cdots\subsetneq A_k$ of $k+1$ members. It is saturated when it is $k$-Sperner and adjoining any missing set $S\in2^X\setminus\mathcal F$ creates such a chain. Thus saturation is maximality under inclusion of families, not largest possible cardinality. Let $\operatorname{sat}_k(n)$ be the smallest cardinality of a saturated $k$-Sperner family when $|X|=n$.

The question asks whether its exponential growth for sufficiently large ground sets has an exponent strictly greater than $1/2$. A precise quantified form of the source's asymptotic assertion is: do there exist $c>1/2$, a function $n_0:\mathbb N\to\mathbb N$, and nonnegative real numbers $\eta_k\to0$ such that, for all sufficiently large $k$ and all $n\ge n_0(k)$, \[ \operatorname{sat}_k(n)\ge 2^{(c-\eta_k)k}? \] One may increase $n_0(k)$ to ensure $n\ge k$ without altering the problem. The error term is controlled by $k$ uniformly throughout the permitted range of $n$, rather than separately for individual ground-set sizes.

The requested improvement is in the exponential rate. A multiplicative factor polynomial in $k$ in front of $2^{k/2}$ does not by itself give a constant $c>1/2$. Both the absence of a chain and the creation of a chain by every possible addition are essential to the minimum-size problem.

Short English statement

For large ground sets, must every saturated family with no chain of length $k+1$ have exponential size with rate strictly above one half?

Research attempt: a saturated construction and a counting barrier

Scope and literature check.

GPT-6 Astra Ultra, 1 October 2026. Saturated means inclusion-maximal among families with no $(k+1)$-chain; it does not mean a family of maximum size. Morrison--Noel--Scott [S3] give constructions smaller than the formerly proposed $2^{k-1}$. Martin--Veldt [S4], published in 2025, improve the asymptotic lower bound to $\sqrt{k}2^{k/2}$ in the relevant large-ground-set regime. That polynomial factor does not give a fixed exponent greater than $1/2$. We verify an elementary construction and examine why a natural counting argument stops there.

1. A complete saturation certificate with $2^{k-1}$ sets.

Let $k\ge2$, choose $Y\subset X$ with $|Y|=k-2$, and put $R=X\setminus Y$, assuming $R\ne\varnothing$. Define \[ \mathcal F=\{A:A\subseteq Y\}\ \cup\ \{A\cup R:A\subseteq Y\}. \] These two parts are disjoint, so $|\mathcal F|=2^{k-1}$. A chain contained in one part has at most $k-1$ members. A chain that uses both parts has a last lower member $A$ and a first upper member $B\cup R$, where $A\subseteq B\subseteq Y$. Its length is at most \[ (|A|+1)+(|Y|-|B|+1)\le |Y|+2=k. \] Hence $\mathcal F$ is $k$-Sperner.

Now let $S\notin\mathcal F$. Necessarily $S\cap R$ is a nonempty proper subset of $R$; put $A=S\cap Y$. A maximal chain from $\varnothing$ to $A$ contributes $|A|+1$ lower members. Follow it by $S$, then by a maximal chain from $A\cup R$ to $X$, contributing $|Y|-|A|+1$ upper members. All inclusions at $S$ are strict. The result has $|Y|+3=k+1$ members. This proves saturation against every possible addition, rather than merely against typical subsets. When $|R|=1$ there are no missing sets; the family is the whole Boolean lattice on $k-1$ points, and the same conclusion is valid.

2. A lower bound for the antichain route.

Let $\mathcal A$ be a saturated antichain on an $n$-element set, with $a\le|A|\le n-b$ for every $A\in\mathcal A$. Every subset $S$ is comparable to at least one member of $\mathcal A$: otherwise it could be added while preserving the antichain condition. Choose $S$ by independent fair inclusion of the $n$ elements. For fixed $A$, the probabilities of $A\subseteq S$ and $S\subseteq A$ are $2^{-|A|}$ and $2^{-(n-|A|)}$, respectively. Their intersection is $S=A$, of probability $2^{-n}$. Therefore the union bound proves \[ 1\le\sum_{A\in\mathcal A} \left(2^{-|A|}+2^{-(n-|A|)}-2^{-n}\right) \le|\mathcal A|(2^{-a}+2^{-b}), \] and consequently $|\mathcal A|\ge(2^{-a}+2^{-b})^{-1}$. For $a=b=\lfloor k/2\rfloor$ this is only $2^{\lfloor k/2\rfloor-1}$. No choice of a polynomial multiplier changes the limiting base-two exponent divided by $k$.

Verification and first remaining gap.

The construction's chain bound explicitly counts a possible jump from the lower copy to the upper copy; treating those copies as unrelated antichains would be wrong. A direct Boolean-lattice check for $k=2,3,4$ and $|X|=k+1$ verified the maximum chain length and every missing-set witness. The antichain estimate is not asserted for an arbitrary $k$-Sperner family: extracting an antichain with controlled ranks is a separate issue. Even on that route the estimate charges overlapping comparability events separately. Improving their overlap accounting by an exponential factor, uniformly in $k$, is the first unproved step towards the requested exponent.

Reproduction of finite checks.

The finite checks stated above were run with Python 3 using the repository script [C1]. They verify the stated examples and finite ranges only.

Final status

UNRESOLVED. The explicit family is a verified, previously familiar upper-bound construction; the antichain counting estimate identifies an obstruction and does not improve the known exponential rate. No new bound stronger than [S4] or numerical completion claim is made.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3068 (OPG-59928), OpenGarden collection. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problem Garden, Saturated $k$-Sperner Systems of Minimum Size. Original problem and discussion; the mathematical formulation below is expanded from the supplied source record. http://www.openproblemgarden.org/op/saturated_k_sperner_systems_of_minimum_size.
• S3 N. Morrison, J. A. Noel and A. Scott, On Saturated $k$-Sperner Systems, arXiv:1402.5646. Original research, checked 1 October 2026. https://arxiv.org/abs/1402.5646.
• S4 R. R. Martin and N. Veldt, Saturation of $k$-Chains in the Boolean Lattice, Electronic Journal of Combinatorics 32$1$ $2025$, P1.55; author preprint arXiv:2402.14113. Checked 1 October 2026. https://arxiv.org/abs/2402.14113.
• C1 Reproducible finite-check code, executed 1 October 2026 with Python 3 (standard library only): scripts/check_attempt_batch_geometry_2026_10_01.py.