A retrospective look at the Erdös-DeBruijn theorem (Q1361671)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A retrospective look at the Erdös-DeBruijn theorem |
scientific article |
Statements
A retrospective look at the Erdös-DeBruijn theorem (English)
0 references
24 November 1997
0 references
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.
0 references
pairwise balanced design
0 references
perfect covering
0 references
perfect packing
0 references