Block design


In combinatorial mathematics, a block design is a set together with a family of subsets whose members are chosen to satisfy some set of properties that are deemed useful for a particular application. These applications come from many areas, including experimental design, finite geometry, physical chemistry, software testing, cryptography, and algebraic geometry. Many variations have been examined, but the most intensely studied are the balanced incomplete block designs which historically were related to statistical issues in the design of experiments.
A block design in which all the blocks have the same size is called uniform. The designs discussed in this article are all uniform. Pairwise balanced designs are examples of block designs that are not necessarily uniform.

Definition of a BIBD (or 2-design)

Given a finite set X and integers k, r, λ ≥ 1, we define a 2-design B to be a family of k-element subsets of X, called blocks, such that any x in X is contained in r blocks, and any pair of distinct points x and y in X is contained in λ blocks.
"Family" in the above definition can be replaced by "set" if repeated blocks are not allowed. Designs in which repeated blocks are not allowed are called simple.
Here v, b, k, r, and λ are the parameters of the design. In a table:
The design is called a -design or a -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
obtained by counting the number of pairs where B is a block and p is a point in that block, and
obtained from the count of triples where p and q are distinct points and B is a block that contains them both, and dividing this count by v.
These conditions are not sufficient as, for example, a -design does not exist.
The order of a 2-design is defined to be n = r − λ. The complement of a 2-design is obtained by replacing each block with its complement in the point set X. It is also a 2-design and has parameters v′ = v, b′ = b, r′ = b − r, k′ = v − k, λ′ = λ + b − 2r. A 2-design and its complement have the same order.
A fundamental theorem, Fisher's inequality, named after the statistician Ronald Fisher, is that b ≥ v in any 2-design.

Examples

The unique -design has 10 blocks and each element is repeated 5 times. Using the symbols 0 − 5, the blocks are the following triples:
One of four nonisomorphic -designs has 14 blocks with each element repeated 7 times. Using the symbols 0 − 7 the blocks are the following 4-tuples:
The unique -design has 7 blocks with each element repeated 3 times. Using the symbols 0 − 6, the blocks are the following triples:

Symmetric BIBDs

The case of equality in Fisher's inequality, that is, a 2-design with an equal number of points and blocks, is called a symmetric design. Symmetric designs have the smallest number of blocks among all the 2-designs with the same number of points.
In a symmetric design r = k holds as well as b = v, and, while it is generally not true in arbitrary 2-designs, in a symmetric design every two distinct blocks meet in λ points. A theorem of Ryser provides the converse. If X is a v-element set, and B is a v-element set of k-element subsets, such that any two distinct blocks have exactly λ points in common, then is a symmetric block design.
The parameters of a symmetric design satisfy
This imposes strong restrictions on v, so the number of points is far from arbitrary. The Bruck–Ryser–Chowla theorem gives necessary, but not sufficient, conditions for the existence of a symmetric design in terms of these parameters.
The following are important examples of symmetric 2-designs:

Projective planes

are symmetric 2-designs with λ = 1 and order n > 1. For these designs the symmetric design equation becomes:
Since k = r we can write the order of a projective plane as n = k − 1 and, from the displayed equation above, we obtain v = n + 1 = n2 + n + 1 points in a projective plane of order n.
As a projective plane is a symmetric design, we have b = v, meaning that b = n2 + n + 1 also. The number b is the number of lines of the projective plane. There can be no repeated lines since λ = 1, so a projective plane is a simple 2-design in which 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. Similarly, r = n + 1 is the number of lines with which 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.
Projective planes are known to exist for all orders which are prime numbers or powers of primes. They form the only known infinite family of symmetric block designs.

Biplanes

A biplane or biplane geometry is a symmetric 2-design with λ = 2; that is, every set of two points is contained in two blocks, while any two lines intersect in two points. They are similar to finite projective planes, except that rather than two points determining one line, two points determine two lines. A biplane of order n is one whose blocks have k = n + 2 points; it has v = 1 + /2 points.
The 18 known examples are listed below.
Biplanes of orders 5, 6, 8 and 10 do not exist, as shown by the Bruck-Ryser-Chowla theorem.

Hadamard 2-designs

An Hadamard matrix of size m is an m × m matrix H whose entries are ±1 such that HH⊤ = mIm, where H⊤ is the transpose of H and Im is the m × m identity matrix. An Hadamard matrix can be put into standardized form where the first row and first column entries are all +1. If the size m > 2 then m must be a multiple of 4.
Given an Hadamard matrix of size 4a in standardized form, remove the first row and first column and convert every −1 to a 0. The resulting 0–1 matrix M is the incidence matrix of a symmetric 2- design called an Hadamard 2-design.
It contains blocks/points; each contains/is contained in points/blocks. Each pair of points is contained in exactly blocks.
This construction is reversible, and the incidence matrix of a symmetric 2-design with these parameters can be used to form an Hadamard matrix of size 4a.

Resolvable 2-designs

A resolvable 2-design is a BIBD whose blocks can be partitioned into sets, each of which forms a partition of the point set of the BIBD. The set of parallel classes is called a resolution of the design.
If a 2- resolvable design has c parallel classes, then b ≥ v + c − 1.
Consequently, a symmetric design can not have a non-trivial resolution.
Archetypical resolvable 2-designs are the finite affine planes. A solution of the famous 15 schoolgirl problem is a resolution of a 2- design.

Generalization: ''t''-designs


Given any positive integer t, a t-design B is a class of k-element subsets of X, 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, b, k, r, λ, and t are the parameters of the design. The design may be called a t--design. Again, these four numbers determine b and r and the four numbers themselves cannot be chosen arbitrarily. The equations are
where λi is the number of blocks that contain any i-element set of points.
Note that.
Theorem: Any t--design is also an s--design for any s with 1 ≤ s ≤ t.
A consequence of this theorem is that every t-design with t ≥ 2 is also a 2-design.
A t--design is called a Steiner system.
The term block design by itself usually means a 2-design.

Derived and extendable t-designs

Let D = be a t- design and p a point of X. The derived design Dp has point set X − and as block set all the blocks of D which contain p with p removed. It is a - design. Note that derived designs with respect to different points may not be isomorphic. A design E is called an extension of D if E has a point p such that Ep is isomorphic to D; we call D extendable if it has an extension.
Theorem: If a t- design has an extension, then k + 1 divides b.
The only extendable projective planes are those of orders 2 and 4.
Every Hadamard 2-design is extendable.
Theorem:.
If D, a symmetric 2- design, is extendable, then one of the following holds:
  1. D is an Hadamard 2-design,
  2. v = , k = λ2 + 3λ + 1,
  3. v = 495, k = 39, λ = 3.
Note that the projective plane of order two is an Hadamard 2-design; the projective plane of order four has parameters which fall in case 2; the only other known symmetric 2-designs with parameters in case 2 are the order 9 biplanes, but none of them are extendable; and there is no known symmetric 2-design with the parameters of case 3.

Inversive planes

A design with the parameters of the extension of an affine plane, i.e., a 3- design, is called a finite inversive plane, or Möbius plane, of order n.
It is possible to give a geometric description of some inversive planes, indeed, of all known inversive planes. An ovoid in PG is a set of q2 + 1 points, no three collinear. It can be shown that every plane of PG meets an ovoid O in either 1 or q + 1 points. The plane sections of size q + 1 of O are the blocks of an inversive plane of order q. Any inversive plane arising this way is called egglike. All known inversive planes are egglike.
An example of an ovoid is the elliptic quadric, the set of zeros of the quadratic form
where f is an irreducible quadratic form in two variables over GF. .
If q is an odd power of 2, another type of ovoid is known – the Suzuki–Tits ovoid.
Theorem. Let q be a positive integer, at least 2. If q is odd, then any ovoid is projectively equivalent to the elliptic quadric in a projective geometry PG; so q is a prime power and there is a unique egglike inversive plane of order q. if q is even, then q is a power of 2 and any inversive plane of order q is egglike.

Partially balanced designs (PBIBDs)

An n-class association scheme consists of a set X of size v together with a partition S of X × X into n + 1 binary relations, R0, R1,..., Rn. A pair of elements in relation Ri are said to be ith-associates. Each element of X has ni ith associates. Furthermore:
An association scheme is commutative if for all i, j and k. Most authors assume this property.
A partially balanced incomplete block design with n associate classes is a block design based on a v-set X with b blocks each of size k and with each element appearing in r blocks, such that there is an association scheme with n classes defined on X where, if elements x and y are ith associates, 1 ≤ i ≤ n, then they are together in precisely λi blocks.
A PBIBD determines an association scheme but the converse is false.

Example

Let A be the following association scheme with three associate classes on the set X =. The entry is s if elements i and j are in relation Rs.

123456
1 0 1 1 2 3 3
2 1 0 1 3 2 3
3 1 1 0 3 3 2
4 2 3 3 0 1 1
5 3 2 3 1 0 1
6 3 3 2 1 1 0


The blocks of a PBIBD based on A are:


The parameters of this PBIBD are: v = 6, b = 8, k = 3, r = 4 and λ1 = λ2 = 2 and λ3 = 1. Also, for the association scheme we have n0 = n2 = 1 and n1 = n3 = 2.

Properties

The parameters of a PBIBD satisfy:
A PBIBD is a BIBD and a PBIBD in which λ1 = λ2 is a BIBD.

Two associate class PBIBDs

PBIBDs have been studied the most since they are the simplest and most useful of the PBIBDs. They fall into six types based on a classification of the then known PBIBDs by :
  1. group divisible;
  2. triangular;
  3. Latin square type;
  4. cyclic;
  5. partial geometry type;
  6. miscellaneous.

    Applications

The mathematical subject of block designs originated in the statistical framework of design of experiments. These designs were especially useful in applications of the technique of analysis of variance. This remains a significant area for the use of block designs.
While the origins of the subject are grounded in biological applications, the designs are used in many applications where systematic comparisons are being made, such as in software testing.
The incidence matrix of block designs provide a natural source of interesting block codes that are used as error correcting codes. The rows of their incidence matrices are also used as the symbols in a form of pulse-position modulation.

Statistical application

Suppose that skin cancer researchers want to test three different sunscreens. They coat two different sunscreens on the upper sides of the hands of a test person. After a UV radiation they record the skin irritation in terms of sunburn. The number of treatments is 3 and the block size is 2.
A corresponding BIBD can be generated by the R-function design.bib of the and is specified in the following table:
PlotsBlockTreatment
10113
10212
20121
20223
30132
30231

The investigator chooses the parameters, and for the block design which are then inserted into the R-function. Subsequently, the remaining parameters and are determined automatically.
Using the basic relations we calculate that we need blocks, that is, 3 test people in order to obtain a balanced incomplete block design. Labeling the blocks and, to avoid confusion, we have the block design,
A corresponding incidence matrix is specified in the following table:
TreatmentBlock ABlock BBlock C
1011
2101
3110

Each treatment occurs in 2 blocks, so.
Just one block contains the treatments 1 and 2 simultaneously and the same applies to the pairs of treatments and. Therefore,.
It is impossible to use a complete design in this example because there are 3 sunscreens to test, but only 2 hands on each person.