BLOCK DESIGN

In combinatorial mathematics, a 'block design' (more fully, a 'balanced incomplete block design') is a particular kind of set system, which has long-standing applications to experimental design (an area of statistics) as well as purely combinatorial aspects.
Given a finite set ''X'' (of elements called points) and integers ''k'', ''r'', λ ≥ 1, we define a '2-design' ''B'' to be a set of ''k''-element subsets of ''X'', called 'blocks', such that the number ''r'' of blocks containing ''x'' in ''X'' is independent of ''x'', and the number λ of blocks containing given distinct points ''x'' and ''y'' in ''X'' is also independent of the choices.
Here ''v'' (the number of elements of ''X'', called points), ''b'' (the number of blocks), ''k'', ''r'', and λ are the 'parameters' of the design. (Also, ''B'' may not consist of all ''k''-element subsets of ''X''; that is the meaning of ''incomplete''.) The design is called a '(''v'', ''k'', λ)-design' or a '(''v'', ''b'', ''r'', ''k'', λ)-design'. The parameters are not all independent; ''v'', ''k'', and λ determine ''b'' and ''r'', and not all combinations of ''v'', ''k'', and λ are possible. The two basic equations connecting these parameters are
:$bk\; =\; vr,$
:$lambda(v-1)\; =\; r(k-1).$
A fundamental theorem ('Fisher's inequality') is that ''b'' ≥ ''v'' in any block design. The case of equality is called a symmetric design; it has many special features.
Examples of block designs include the lines in finite projective planes (where ''X'' is the set of points of the plane and λ = 1), and Steiner triple systems (''k'' = 3). The former is a relatively simple example of a symmetric design.

Contents

Generalization: ''t''-designs

References

Generalization: ''t''-designs

Given any integer ''t'' ≥ 2, a '''t''-design' ''B'' is a class of ''k''-element subsets of ''X'' (the set of points) , called 'blocks', such that the number ''r'' of blocks that contain any point ''x'' in ''X'' is independent of ''x'', and the number λ of blocks that contain any given ''t''-element subset ''T'' is independent of the choice of ''T''. The numbers ''v'' (the number of elements of ''X''), ''b'' (the number of blocks), ''k'', ''r'', λ, and ''t'' are the 'parameters' of the design. The design may be called a '''t''-(''v'',''k'',λ)-design'. Again, these four numbers determine ''b'' and ''r'' and the four numbers themselves cannot be chosen arbitrarily. The equations are
:
where ''b_i'' is the number of blocks that contain any ''i''-element set of points.
Examples include the ''d''-dimensional subspaces of a finite projective geometry (where ''t'' = ''d'' + 1 and λ = 1).
The term ''block design'' by itself usually means a 2-design.

References

★ van Lint, J.H., and R.M. Wilson (1992), ''A Course in Combinatorics''. Cambridge, Eng.: Cambridge University Press.

★