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, named after Ronald Fisher, 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.

Projective planes

Projective planes are a special case of block designs, where we have $scriptstyle\; v\; ,>,\; 0$ points and, as they are symmetric designs, $scriptstyle\; b\; ,=,\; v$ (which is the limit case of Fisher's inequality), from the first basic equation we get

:$k\; =\; r,\; ,$

and since $scriptstyle\; lambda\; ,=,\; 1$ by definition, the second equation gives us

:$v-1\; =\; k(k-1).,$

Now, given an integer $scriptstyle\; n\; ,geq,\; 1$, called the "order of the projective plane", we can put "k" = "n" + 1 and, from the displayed equation above, we have $scriptstyle\; v\; ,=,\; (n+1)n\; ,+,\; 1\; ,=,\; n^2\; ,+,\; n\; ,+,\; 1$ points in a projective plane of order "n".

Since a projective plane is symmetric, we have that $scriptstyle\; b\; ,=,\; v$, which means that $scriptstyle\; b\; ,=,\; n^2\; ,+,\; n\; ,+,\; 1$ also. The number "b" is usually called the number of "lines" of the projective plane.

This means, as a corollary, that in a projective plane, the number of lines and the number of points are always the same. For a projective plane, "k" is the number of lines and it is equal to "n" + 1, where "n" is the order of the plane. Similarly, "r" = "n" + 1 is the number of lines to which the a given point is incident.

For "n" = 2 we get a projective plane of order 2, also called the Fano plane, with "v" = 4 + 2 + 1 = 7 points and 7 lines. In the Fano plane, each line has "n" + 1 = 3 points and each point belongs to "n" + 1 = 3 lines.

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.

There are no known examples of non-trivial "t"-("v","k",1)-designs with $scriptstyle\; t\; >,\; 5$.

The term "block design" by itself usually means a 2-design.

ee also

* Randomized block design

References

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