Problem Statement
Let $k>r$ and $n$ be sufficiently large in terms of $k$ and $r$. Does there always exist a block $r-(n,k,1)$ design (or Steiner system with parameters $(n,k,r)$), provided the trivial necessary divisibility conditions $\binom{k-i}{r-i}\mid \binom{n-i}{r-i}$ are satisfied for every $0\leq i<r$?
That is, can one find a family of $\binom{n}{k}\binom{k}{r}^{-1}$ many subsets of $\{1,\ldots,n\}$, all of size $k$, such that any $A\subseteq \{1,\ldots,n\}$ of size $r$ is contained in exactly one set in the family?
That is, can one find a family of $\binom{n}{k}\binom{k}{r}^{-1}$ many subsets of $\{1,\ldots,n\}$, all of size $k$, such that any $A\subseteq \{1,\ldots,n\}$ of size $r$ is contained in exactly one set in the family?
Categories:
Combinatorics
Progress
This was proved for $(r,k)$ by:- Kirkman for $(2,3)$;
- Hanani [Ha61] for $(3,4)$, $(2,4)$, and $(2,5)$;
- Wilson [Wi72] for $(2,k)$ for any $k$;
- Keevash [Ke14] for all $(r,k)$.
Source: erdosproblems.com/722 | Last verified: January 16, 2026