We consider t-designs with *=1 (generalized Steiner systems) for which the block size is not necessarily constant. An inequality for the number of blocks is derived. For t=2, this inequality is the well known De Bruijn Erdo s inequality. For t>2 it has the same order of magnitude as the Wilson Petrenjuk inequality for Steiner systems with constant block size. The point of this note is that the inequality is very easy to derive and does not seem to be known. A stronger inequality was derived in 1969 by Woodall (J. London Math. Soc. (2) 1, 509 519), but it requires Lagrange multipliers in the proof.
1997 Academic Press
We consider a so-called generalized Steiner system t&(n, V, 1), i.e., a collection B of subsets (blocks) of an n-set P (of n points) with the property that every t-subset of P is contained in exactly one block in B.
We represent such a system by a (0,1)-matrix A of size b by n, with b := |B|, where the i th row of A is the characteristic function of the i th block B i # B.
A generalized Steiner system is called trivial if |B| =1.
Definition. We define ; t, n to be the minimal number of blocks in a nontrivial system t&(n, V, 1).
Theorem. For t 2 we have ; t, n (; t, n &1) t \ n t + .
Proof. The proof is by induction. The case t=2 is the well known Erdo s-De Bruijn inequality (if t=2 and |B| >1, then |B| n; cf.