Wiki
Wiki

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

Updated


Claim. For every n≡1n\equiv1 or 3(mod6)3\pmod 6 there is a family of 33-subsets of an nn-element set containing every 22-subset exactly once, a Steiner triple system S(2,3,n)S(2,3,n); the congruence is necessary, since 2∣n−12\mid n-1 and 6∣n(n−1)6\mid n(n-1) are the divisibility conditions of Problem 722 for (r,k)=(2,3)(r,k)=(2,3). Kirkman's paper, On a problem in combinations, sets out to determine the greatest number of triples on a given number of symbols in which no pair is used twice, and for the numbers ≡1,3(mod6)\equiv1,3\pmod 6 its construction uses every pair exactly once. Keevash's survey of earlier work reads the paper as settling the case (q,r)=(3,2)(q,r)=(3,2) of the existence conjecture before Steiner posed his problem, and Erdős says the same in [Er81], Part VI, where he calls the case r=2r=2, k=3k=3 settled by Kirkman. Hanani's paper on quadruple systems, Hanani's quadruple systems, credits the sufficiency of the congruence to Reiss (1859) and Moore (1893), who proved it again without knowing Kirkman's paper. The site credits the case to Kirkman without a reference key.

Covers. The case (r,k)=(2,3)(r,k)=(2,3) of the problem, for every nn: the divisibility conditions, n≡1n\equiv1 or 3(mod6)3\pmod 6, suffice for a Steiner system S(2,3,n)S(2,3,n). The paper says nothing about any other pair (r,k)(r,k); the general case is Keevash's existence of designs.

Acceptance. Refereed: T. P. Kirkman, On a problem in combinations, Cambridge and Dublin Math. J. 2 (1847), 191–204, a journal publication; the volume gives the year only, and the page is dated to its first day. The site's curator names Kirkman's case 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.