Block design

A system of subsets of a finite set which satisfies certain conditions related to the frequency of appearance of pairs of elements of the set in the subsets of the system. The concept of a block design arose in the theory of design (planning) of (statistical) experiments in the 1920s and 1930s, but had been studied as early as the mid-19th century under the name tactical configurations. The concept of a block design is a variation of the concepts of a hypergraph, a net and a complex. As a rule, in a block design several additional limitations are imposed on the family of subsets. A block design may be defined by a pair of sets $ (V,\ B) $ where

$$ V \ = \ \{ a _ {1} \dots a _ {v} \} ,\ \ B \ = \ \{ B _ {1} \dots B _ {b} \} , $$

$$ B _ {i} \ \subseteq \ V,\ \ i = 1 \dots b. $$

The elements of the set $ V $ are called the points (treatments) of the block design, or varieties or elements, while the elements of the set $ B $ are called its blocks. The element $ a _ {i} $ and the block $ B _ {j} $ are incident if $ a _ {i} \in B _ {j} $. The number $ | B _ {j} | $ of elements incident with $ B _ {j} $ is usually denoted by $ k _ {j} $, while the number of blocks incident with $ a _ {i} $ is denoted by $ r _ {i} $. The number

$$ | \{ {B _ j} : {a _ {i} \in B _ {j} ,\ a _ {l} \in B _ j} \} | $$

is denoted by $ \lambda _ {il} $. The numbers $ v,\ b,\ r _ {i} $, $ k _ {j} $, $ \lambda _ {il} $( $ i,\ l = 1 \dots v $; $ j = 1 \dots b $) are said to be the parameters of the block design. If $ r _ {i} = r $ for all $ i = 1 \dots v $, $ k _ {j} = k $ for all $ j = 1 \dots b $ and $ \lambda _ {il} = \lambda $, $ (V,\ B) $ is a balanced incomplete block design (BIBD) with parameters $ v $, $ b $, $ r $, $ k $, $ \lambda $. The meaning of the word "balanced" is that the frequencies of appearance of all elements and pairs of elements in the blocks are respectively equal, while the word "incomplete" indicates that, generally speaking, not all the $ k $- element sets are included in $ B $.

Let exactly $ m $ different numbers $ \lambda _ {1} \dots \lambda _ {m} $ be encountered among the numbers $ \lambda _ {il} $, $ i,\ l = 1 \dots v $, and let $ m $ symmetric association relations be introduced on the elements of the set $ V $ so that the following conditions are satisfied:

1) the set $ V ^ {2} $ of all pairs of distinct elements of $ V $ is subdivided into $ m $ disjoint subsets $ V _ {1} ^ {2} \dots V _ {m} ^ {2} $ and, if $ (a,\ a ^ \prime ) \in V _ {j} ^ {2} $, then $ a $ and $ a ^ \prime $ are said to be $ j $- associated;

2) $ | \{ {B _ j} : {a \in B _ {j} ,\ a ^ \prime \in B _ {j} ,\ (a,\ a ^ \prime ) \in V _ {i} ^ {2}} \} | = \lambda _ {i} $, $ i = 1 \dots m $, $ j = 1 \dots b $;

3) $ | \{ {a} : {\exists a ^ \prime \ (a,\ a ^ \prime ) \in V _ {i} ^ {2}} \} | = n _ {i} $, $ i = 1 \dots m $;

4) $ | \{ {a ^ {\prime\prime}} : {(a ^ {\prime\prime} ,\ a) \in V _ {j} ^ {2} ,\ (a ^ {\prime\prime} ,\ a ^ \prime ) \in V _ {k} ^ {2} ,\ (a,\ a ^ \prime ) \in V _ {i} ^ {2}} \} | = p _ {jk} ^ {i} $, and, in view of the symmetry, $ p _ {jk} ^ {i} = p _ {kj} ^ {i} $, $ i,\ j,\ k = 1 \dots m $. A block design with the properties 1)–4) is said to be a partial balanced incomplete block design with $ m $ types of relations or a PBIB( $ m $)- design. The rule which specifies the association relation is called the association design. A BIB-design is a PBIB( $ 1 $)- design. An example of a PBIB( $ 2 $)- design is a block design which may be represented as the table

$$ \begin{array}{r} 1 \\ 4 \\ 7 \\ 10 \end{array} \ \ \begin{array}{r} 1 \\ 5 \\ 8 \\ 11 \end{array} \ \ \begin{array}{r} 1 \\ 6 \\ 9 \\ 12 \end{array} \ \ \begin{array}{r} 2 \\ 4 \\ 9 \\ 11 \end{array} \ \ \begin{array}{r} 2 \\ 5 \\ 7 \\ 12 \end{array} \ \ \begin{array}{r} 2 \\ 6 \\ 8 \\ 10 \end{array} \ \ \begin{array}{r} 3 \\ 4 \\ 8 \\ 12 \end{array} \ \ \begin{array}{r} 3 \\ 5 \\ 9 \\ 10 \end{array} \ \ \begin{array}{r} 3 \\ 6 \\ 7 \\ 11 \end{array} , $$

where any two numbers in the same column are $ 1 $- associated, while any two numbers in different columns are $ 2 $- associated. Here $ v = 12 $, $ b = 9 $, $ r = 3 $, $ k = 4 $, $ \lambda _ {1} = 1 $, $ \lambda _ {2} = 0 $, $ n _ {1} = 9 $, $ n _ {2} = 2 $.

$$ P ^ {1} \ = \ \| p _ {jk} ^ {1} \| \ = \ \left \| {6 \atop 2} \ {2 \atop 0} \ \right \| ,\ \ P ^ {2} \ = \ \| p _ {jk} ^ {2} \| \ = \ \left \| {9 \atop 0} \ {0 \atop 1} \ \right \| . $$

To each block design with $ v $ elements and $ b $ blocks corresponds an incidence matrix $ A = \| c _ {ij} \| $, where $ c _ {ij} = 1 $ if $ a _ {i} \in B _ {j} $ and $ c _ {ij} = 0 $ otherwise, $ i = 1 \dots v $; $ j = 1 \dots b $. The theory of block designs considers problems on the existence and classification as well as problems involved in the construction of a block design with given parameters. The parameters of a block design are related in a certain manner. The following equations are valid for BIB-designs:

$$ \tag{1} vr \ = \ kb, $$

$$ \lambda (v-1) \ = \ r (k-1). $$

Equation (1) and the relationships

$$ \sum _ { i=1 } ^ m n _ {i} \ = \ v - 1, $$

$$ \sum _ {i = 1} ^ m \lambda _ {i} n _ {i} \ = \ r (k - 1), $$

$$ \sum _ {k = 1} ^ m p _ {jk} ^ {i} \ = \ \left \{ \ { n _ {j}\qquad \textrm{ if }i \neq j ,\qquad\qquad \atop n _ {j} - 1 \ \ \textrm{ if } \ i = j,\ i,\ j = 1 \dots m,} \quad \textrm { with }\quad n _ {i} p _ {jk} ^ {i} \ = \ n _ {j} p _ {ik} ^ {j} \ = \ n _ {k} p _ {ij} ^ {k} ,\ \ i,\ j,\ k = 1 \dots m, \right .$$

are valid for the parameters of PBIB( $ m $)- designs. The incidence matrix of a BIB-design satisfies the fundamental matrix relation

$$ \tag{2} A A ^ {T} \ = \ (r - \lambda ) E + \lambda J , $$

where $ E $ is the unit matrix of order $ v $ and $ J $ is the matrix of order $ v $ consisting exclusively of ones. The existence of a $ (0,\ 1) $- matrix which satisfies condition (2) is a sufficient condition for the existence of a BIB-design with the given parameters. The Fisher inequality $ b \geq v $ follows from (2). A BIB-design for which $ b = v $( i.e. also $ r = k $) is said to be a symmetric design or a $ (v,\ k,\ \lambda ) $- configuration. The following theorem applies to symmetric BIB-designs: If there exists a symmetric BIB-design with parameters $ v $, $ k $, $ \lambda $, then: 1) if $ v $ is even, $ k - \lambda $ is a perfect square; 2) if $ v $ is odd, the equation

$$ z ^ {2} \ = \ (k - \lambda ) x ^ {2} + (-1) ^ {(v-1)/2} \lambda y ^ {2} $$

has a solution in integers $ x,\ y,\ z $, not all of which are zero. The conditions of this theorem are sufficient for the existence of a rational matrix $ A $ satisfying equation (2).

A special range of problems involving the existence of BIB-designs arises in the context of the following problem: Given $ b $ blocks, find the conditions necessary for the completion of these blocks to form a BIB-design. In their most general form these conditions are expressed as the requirement of positive definiteness of some quadratic form $ Q $, as well as the possibility of representing $ Q $ as a sum of squares of linear forms with non-negative coefficients.

The following subclasses of BIB-designs have been most extensively studied: Steiner systems (BIB-designs with $ \lambda = 1 $), in particular Steiner triple systems ( $ k = 3 $); Hadamard configurations ( $ v = b = 4t - 1 $, $ r = k = 2t - 1 $, $ \lambda = t - 1 $, $ t\geq 2 $), the incidence matrix of which is obtained from a Hadamard matrix; affine finite geometries and projective finite geometries [1]. In the class of PBIB-designs those most extensively studied are PBIB( $ 2 $)- designs, which may be subdivided according to their association design into group-divisible block designs, triangular block designs, Latin square block designs, cyclic block designs, etc. [3].

The methods for constructing block designs are usually classified as direct and recursive. The latter methods make it possible to use designs with smaller parameter values to construct designs with larger parameter values. The direct methods mostly utilize the properties of finite fields or some geometric properties.

Block designs are used in the design of experiments, the theory of games, graph theory and in the construction of error-correcting codes.

References

[1]	H.J. Ryser, "Combinatorial mathematics" , Wiley (1963)
[2]	M. Hall, "Combinatorial theory" , Blaisdell (1967)
[3]	S.A. Shirokova, "Block designs" Russian Math. Surveys , 23 : 5 (1968) pp. 47–94 Uspekhi Mat. Nauk , 23 : 5 (1968) pp. 51–98

Comments

The theorem giving conditions on the numbers $ v,\ k,\ \lambda $ in order that a symmetric BIB-design with these numbers as parameters exists, is called the Bruck–Ryser–Chowla theorem.