A retrospective look at the Erdös-DeBruijn theorem (Q1361671)

A pairwise balanced design (PBD) is a family of blocks from a set \(V = \{1,2,\ldots ,v\}\) such that each pair from \(V\) occurs in exactly \(\lambda\) blocks. The number \(g^k(v)\) denotes the minimum cardinality of a PBD with \(\lambda = 1\) and blocks of size at most \(k\). A unified proof of earlier lower bounds on \(g^{k}(v)\), including a result by \textit{G. N. de Bruijn} and \textit{P. Erdös} [Proc. Akad. Wet. Amsterdam 51, 1277-1279 (1948; Zbl 0032.24405)] showing that \(g^k(v)\geq v\), is obtained in this paper using counting arguments. Other results on \(g^k(v)\) are also extensively surveyed.