Smallest $n$ admitting an antichain on $[n]$ with $n-3$ distinct block sizes, each used $\ge r$ times (Erdős #776)
Statement
Fix $r\ge 2$. Consider families $A_1,\dots,A_m\subseteq\{1,\dots,n\}$ that form an *antichain* ($A_i\not\subseteq A_j$ for $i\neq j$) and satisfy the multiplicity condition: for every $t$, if some set has size $t$ then at least $r$ of the sets have size $t$. The number of *distinct sizes* used is at most $n-1$. Let $n_0(r)$ be the least $n$ for which there exists such a family using exactly $n-3$ distinct sizes. Determine $n_0(r)$, as a function of $r$, for small $r$.
Acceptance. FULLY RESOLVES (for a given small $r$): the exact threshold $n_0(r)$ — (a) an explicit antichain on $\{1,\dots,n_0(r)\}$ meeting the multiplicity condition and using exactly $n_0(r)-3$ distinct sizes (machine-verified antichain + size profile), and (b) a certificate (exhaustive/ILP infeasibility) that no admissible family exists for any $n<n_0(r)$. PARTIAL: verified upper bounds (an explicit admissible family for some $n$, giving $n_0(r)\le n$) or lower bounds (certified infeasibility for a specific $n$).
Background
An extremal set-system problem of Erdős. It refines Sperner/antichain theory by demanding that each realized block size be used with multiplicity $\ge r$ while still spreading the family across nearly all $n-1$ possible sizes (here missing only $3$). For fixed $r$ and $n$ the existence question is a finite feasibility problem — one can search for such an antichain (or prove infeasibility) using the Kruskal–Katona / LYM constraints on the size profile — so the threshold $n_0(r)$ is computable for small $r$. Source: T. F. Bloom, Erdős Problem #776, https://www.erdosproblems.com/776; P. Erdős (1981); R. K. Guy (1983).
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #776 (antichains with prescribed size multiplicities) | link |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.