Block design
In combinatorial mathematics, a block design is an incidence structure consisting of a set together with a family of subsets known as blocks, chosen such that number of occurrences of each element satisfies certain conditions making the collection of blocks exhibit symmetry. Block designs have applications in many areas, including experimental design, finite geometry, physical chemistry, software testing, cryptography, and algebraic geometry.
Without further specifications the term block design usually refers to a balanced incomplete block design, specifically a 2-design, which has been the most intensely studied type historically due to its application in the design of experiments. Its generalization is known as a t-design.
Overview
A design is said to be balanced if all t-subsets of the original set occur in equally many blocks. When t is unspecified, it can usually be assumed to be 2, which means that each pair of elements is found in the same number of blocks and the design is pairwise balanced. For t = 1, each element occurs in the same number of blocks and the design is said to be regular. A block design in which all the blocks have the same size is called uniform or proper. The designs discussed in this article are all uniform. Block designs that are not necessarily uniform have also been studied; for t = 2 they are known in the literature under the general name pairwise balanced designs. Any uniform design balanced up to t is also balanced in all lower values of t, so for example a pairwise balanced design is also regular. When the balancing requirement fails, a design may still be partially balanced if the t-subsets can be divided into n classes, each with its own λ-value. For t = 2 these are known as PBIBD designs, whose classes form an association scheme.Designs are usually said to be incomplete, meaning that the collection of blocks is not all possible k-subsets, thus ruling out a trivial design.
Block designs may or may not have repeated blocks. Designs without repeated blocks are called simple, in which case the "family" of blocks is a set rather than a multiset.
In statistics, the concept of a block design may be extended to non-binary block designs, in which blocks may contain multiple copies of an element. There, a design in which each element occurs the same total number of times is called equireplicate, which implies a regular design only when the design is also binary. The incidence matrix of a non-binary design lists the number of times each element is repeated in each block.
Regular uniform designs (configurations)
The simplest type of "balanced" design is known as a tactical configuration or 1-design. The corresponding incidence structure in geometry is known simply as a configuration, see Configuration. Such a design is uniform and regular: each block contains k elements and each element is contained in r blocks. The number of set elements v and the number of blocks b are related by, which is the total number of element occurrences.Every binary matrix with constant row and column sums is the incidence matrix of a regular uniform block design. Also, each configuration has a corresponding biregular bipartite graph known as its incidence or Levi graph.
Pairwise balanced uniform designs (2-designs or BIBDs)
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. Here, the condition that any x in X is contained in r blocks is redundant, as shown below.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 counting for a fixed x the triples where x and y are distinct points and B is a block that contains them both. This equation for every x also proves that r is constant even without assuming it explicitly, thus proving that the condition that any x in X is contained in r blocks is redundant and r can be computed from the other parameters.
The resulting b and r must be integers, which imposes conditions on v, k, and λ. 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.
A rather surprising and not very obvious combinatorial result for these designs is that if points are denoted by any arbitrarily chosen set of equally or unequally spaced numerics, there is no choice of such a set which can make all block-sums constant. For other designs such as partially balanced incomplete block designs this may however be possible. Many such cases are discussed in. However, it can also be observed trivially for the magic squares or magic rectangles which can be viewed as the partially balanced incomplete block designs.
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:and the corresponding incidence matrix is:
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 is symmetric and has 7 blocks with each element repeated 3 times. Using the symbols 0 − 6, the blocks are the following triples:
This design is associated with the Fano plane, with the elements and blocks of the design corresponding to the points and lines of the plane. Its corresponding incidence matrix can also be symmetric, if the labels or blocks are sorted the right way:
Symmetric 2-designs (SBIBDs)
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.
- The order 0 biplane has 2 points ; it is two points, with two blocks, each consisting of both points. Geometrically, it is the digon.
- The order 1 biplane has 4 points ; it is the complete design with v = 4 and k = 3. Geometrically, the points are the vertices of a tetrahedron and the blocks are its faces.
- The order 2 biplane is the complement of the Fano plane: it has 7 points, where the lines are given as the complements of the lines in the Fano plane.
- The order 3 biplane has 11 points, and is also known as the after Raymond Paley; it is associated to the Paley digraph of order 11, which is constructed using the field with 11 elements, and is the [|Hadamard 2-design] associated to the size 12 Hadamard matrix; see Paley construction I.
- There are three biplanes of order 4. One is the Kummer configuration. These three designs are also Menon designs.
- There are four biplanes of order 7.
- There are five biplanes of order 9.
- Two biplanes are known of order 11.