Block design

From Wikipedia, the free encyclopedia

See block design test for an account of that concept in intelligence testing.

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 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 x and y in X is also independent of the choices. Here v (the number of elements of X), 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.

Examples 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).

Given any integer t ≥ 2, a t-design B is a class of k-element subsets of X, called blocks, such that the number r of blocks that contain any x in X is independent of x and the number λ 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.