Problem 722

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?

Source: erdosproblems.com/722

Combinatorics

Wiki page

Status

SolvedProved

An accepted solution exists. The statement is true.

Proved: the site labels the problem PROVED and records the progression Kirkman for $(r,k)=(2,3)$ , Hanani [Ha61] for $(3,4)$ , $(2,4)$ and $(2,5)$ , Wilson [Wi72] for $(2,k)$ , and Keevash [Ke14] for every $(r,k)$ .

Er81: Erdős, P., On the combinatorial problems which I would most like to see solved. Combinatorica 1 (1981), no. 1, 25–42; Part VI states the problem.
Ki47: Kirkman, T. P., On a problem in combinations. Cambridge and Dublin Math. J. 2 (1847), 191–204. Not in the site's bibliography; the site's commentary credits the case $(2,3)$ to Kirkman without a key.
Ha60: Hanani, H., On quadruple systems. Canad. J. Math. 12 (1960), 145–157, DOI 10.4153/CJM-1960-013-3. Not in the site's bibliography; the site's commentary credits the case $(3,4)$ to Hanani under its key [Ha61], which the site's reference record resolves to the 1961 paper below, on $2$ -designs with block sizes $3$ , $4$ and $5$ ; this paper proves the $(3,4)$ case, and [Er81] attaches that case to the 1961 paper as well.
Ha61: Hanani, Haim, The existence and construction of balanced incomplete block designs. Ann. Math. Statist. 32 (1961), no. 2, 361-386, DOI 10.1214/aoms/1177705047; proves the cases $(2,4)$ and $(2,5)$ .
Ke14: P. Keevash, The existence of designs. arXiv:1401.3665 (2014).
GKLO23: Glock, S., Kühn, D., Lo, A. and Osthus, D., The existence of designs via iterative absorption: hypergraph $F$ -designs for arbitrary $F$ . Mem. Amer. Math. Soc. 284 (2023), no. 1406; arXiv:1611.06827 (2016). Not held.
Wi72: Wilson, Richard M., An existence theory for pairwise balanced designs. II. The structure of PBD-closed sets and the existence conjectures. J. Combinatorial Theory Ser. A 13 (1972), 246-273. The site's commentary credits the case $(2,k)$ to Wilson under this key; Part II states the existence conjectures, and [Wi75] proves them.
Wi75: Wilson, R. M., An existence theory for pairwise balanced designs. III. Proof of the existence conjectures. J. Combin. Theory Ser. A 18 (1975), no. 1, 71–79, DOI 10.1016/0097-3165(75)90067-9. Not in the site's bibliography; [Er81] cites Part III as its [83] but prints the volume and pages of Parts I and II.

Problem 722

Status

Proof claims

Discussion