Block design

Template:For In combinatorial mathematics, a block design is a particular kind of hypergraph or set system, which has applications to experimental design, finite geometry, software testing, cryptography, and algebraic geometry. Many variations have been studied, including balanced incomplete block designs.^[1][2]

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.) In a table:

v	points, number of elements of X
b	blocks
r	number of blocks containing a given point
k	number of points in a block
λ	number of blocks containing 2 (or more generally t) points

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

${\displaystyle bk = vr, \,}$

${\displaystyle \lambda(v-1) = r(k-1). \,}$

These conditions are not sufficient as for example a (43,7,1)-design does not exist. 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[]

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 ${\displaystyle (k = 3}$ and ${\displaystyle \lambda=1)}$. The former is a relatively simple example of a symmetric design. Triple systems ${\displaystyle (k=3)}$ are of interest in their own right.^[3]

Projective planes[]

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

${\displaystyle k = r, \,}$

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

${\displaystyle v-1 = k(k-1).\,}$

Now, given an integer ${\displaystyle \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 ${\displaystyle \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 ${\displaystyle \scriptstyle b \,=\, v}$, which means that ${\displaystyle \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 points on each line 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.

Biplane geometry[]

A biplane geometry or biplane is another type of symmetric design ("projective design"), here with λ = 2 – it is a symmetric design such that any set of two points is contained in two blocks ("lines"), while any two lines intersect in two points;^[4] this is similar to a finite projective plane, except that rather than two points determining one line (and two lines determining one point), they determine two lines (respectively, points). A biplane geometry of order n is one whose blocks have ${\displaystyle k=n+2}$ points, by analogy with a projective plane of order n being one with ${\displaystyle k=n+1}$ points, and similarly for other projective designs. A biplane of order n has ${\displaystyle v=1+(k+2)(k+1)/2}$ points (since ${\displaystyle r=k}$).

As examples:^[5]

• The order 0 biplane has 2 points (and lines of size 2 – (2,2,2)); it is two points, with two blocks, each consisting of both points. Geometrically, it is the digon.

One can also in define trivial biplane geometries of order −1 (1 point, lines of size 1 (2,1,2) – the point is contained in the line) and −2 (1 point, lines of size 0 (2,0,2) – the point is not contained in the line).

• The order 1 biplane has 4 points (and lines of size 3 – (4,3,2)); it is the complete design with v = 4 and k = 3. Geometrically, the points are the vertices and the blocks are the faces of a tetrahedron.
• The order 2 biplane is the complement of the Fano plane: it has 7 points (and lines of size 4 – (7,4,2)), where the lines are given as the complements of the (3-point) lines in the Fano plane.^[6]
• The order 3 biplane has 11 points (and lines of size 5 – (11,5,2)), and is also known as the Template:Visible anchor after Raymond Paley; it is associated to the Paley digraph of order 11, which is constructed using the field with 11 elements, and is associated to the order 12 Hadamard matrix; see Paley construction I.

Algebraically this corresponds to the exceptional embedding of the projective special linear group ${\displaystyle PSL(2,5)}$ in ${\displaystyle PSL(2,11)}$ – see projective linear group: action on p points for details.^[6]

• There are 3 biplanes of order 4 (16 points, lines of size 6 – (16,6,2)).
• There are at least 4 biplanes of order 9 (and 56 points – (56,11,2)).^[7]

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 every point x in X appears in exactly r blocks, and every t-element subset T appears in exactly λ blocks. 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

${\displaystyle b_i = \lambda \left.\binom{v-i}{t-i} \right/ \binom{k-i}{t-i} \text{ for } i = 0,1,\ldots,t, }$

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 ${\displaystyle \scriptstyle t >\, 5}$.

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

See also[]

• Randomized block design

Notes[]

References[]

• van Lint, J.H., and R.M. Wilson (1992), A Course in Combinatorics. Cambridge, Eng.: Cambridge University Press.
• S. S. Shrikhande, and Vasanti N. Bhat-Nayak, Non-isomorphic solutions of some balanced incomplete block designs I – Journal of Combinatorial Theory, 1970
• Template:Cite book
• Template:Cite book
• Template:Cite book
• Template:Mathworld

External links[]

• Design DB: A database of combinatorial, statistical, experimental block designs

Template:Experimental design

de:Blockplan ja:ブロックデザイン (数学) ru:Блок-дизайн