Wiki
Wiki

Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.

Updated


Claim. Hanani's The existence and construction of balanced incomplete block designs proves that the necessary conditions (k−1)∣λ(v−1)(k-1)\mid\lambda(v-1) and k(k−1)∣λv(v−1)k(k-1)\mid\lambda v(v-1) are sufficient for a balanced incomplete block design on vv points, a family of kk-subsets containing every pair of points in exactly λ\lambda blocks, for block size k=3k=3 and k=4k=4 with every index λ\lambda, and for k=5k=5 with λ=1\lambda=1, 44 and 2020, the case k=5k=5, λ=1\lambda=1 with the possible exception of v=141v=141. The exception was removed by Hanani's note A balanced incomplete block design, Ann. Math. Statist. 36 (1965), no. 2, 711, which constructs the design with k=5k=5, λ=1\lambda=1, v=141v=141. Keevash's survey of earlier work reads the paper as answering Steiner's problem for (q,r)∈{(4,2),(5,2)}(q,r)\in\{(4,2),(5,2)\} and all nn. For λ=1\lambda=1 the conditions are the divisibility conditions of Problem 722 for r=2r=2, (k−1)∣(n−1)(k-1)\mid(n-1) and k(k−1)∣n(n−1)k(k-1)\mid n(n-1), that is n≡1n\equiv1 or 4(mod12)4\pmod{12} for k=4k=4 and n≡1n\equiv1 or 5(mod20)5\pmod{20} for k=5k=5, so the answer is yes for (r,k)=(2,4)(r,k)=(2,4) and every nn, and yes for (2,5)(2,5) and every admissible nn except possibly 141141 by this paper, and for every nn with the 1965 note. For k=3k=3 the paper proves again the case Kirkman's triple systems settled. The constructions are recursive, composing designs on smaller point sets through pairwise balanced designs and group divisible designs.

Covers. The cases (r,k)=(2,4)(r,k)=(2,4) and (2,5)(2,5) of the problem, for all large nn: the divisibility conditions suffice for Steiner systems S(2,4,n)S(2,4,n) and, for every n≠141n\ne141, S(2,5,n)S(2,5,n). The paper treats 22-designs only, so it says nothing about (3,4)(3,4), which is Hanani's quadruple systems, or about (2,k)(2,k) for k≥6k\ge6, which is Wilson's existence theorem for large nn.

Acceptance. Refereed: H. Hanani, The existence and construction of balanced incomplete block designs, Ann. Math. Statist. 32 (1961), no. 2, 361–386; the issue is dated June 1961, and the page is dated to the first day of that month. The site's commentary credits the cases (2,4)(2,4) and (2,5)(2,5), and also (3,4)(3,4), to Hanani under its key [Ha61], which resolves to this paper; the (3,4)(3,4) case is proved in his 1960 paper on quadruple systems. The curator names these cases in the progression that ends with Keevash while crediting the problem's PROVED label to Keevash, which does not settle the problem on this result, so the page lists no reviewed evidence. The proof has not been reconstructed or independently reviewed in this corpus.