View source for 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b0166701.png" /> where

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b0166702.png" /></td> </tr></table>

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b0166703.png" /></td> </tr></table>

The elements of the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b0166704.png" /> are called the points (treatments) of the block design, or varieties or elements, while the elements of the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b0166705.png" /> are called its blocks. The element <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b0166706.png" /> and the block <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b0166707.png" /> are incident if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b0166708.png" />. The number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b0166709.png" /> of elements incident with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667010.png" /> is usually denoted by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667011.png" />, while the number of blocks incident with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667012.png" /> is denoted by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667013.png" />. The number

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667014.png" /></td> </tr></table>

is denoted by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667015.png" />. The numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667016.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667017.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667018.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667019.png" />; <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667020.png" />) are said to be the parameters of the block design. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667021.png" /> for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667022.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667023.png" /> for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667024.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667025.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667026.png" /> is a ''[[balanced incomplete block design]]''  (BIBD) with parameters <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667027.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667028.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667029.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667030.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667031.png" />. 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667032.png" />-element sets are included in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667033.png" />.

Let exactly <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667034.png" /> different numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667035.png" /> be encountered among the numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667036.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667037.png" />, and let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667038.png" /> symmetric association relations be introduced on the elements of the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667039.png" /> so that the following conditions are satisfied:

1) the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667040.png" /> of all pairs of distinct elements of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667041.png" /> is subdivided into <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667042.png" /> disjoint subsets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667043.png" /> and, if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667044.png" />, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667045.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667046.png" /> are said to be <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667047.png" />-associated;

2) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667048.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667049.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667050.png" />;

3) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667051.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667052.png" />;

4) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667053.png" />, and, in view of the symmetry, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667054.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667055.png" />. A block design with the properties 1)–4) is said to be a partial balanced incomplete block design with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667057.png" /> types of relations or a  PBIB(<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667059.png" />)-design. The rule which specifies the association relation is called the association design. A BIB-design is a PBIB(<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667060.png" />)-design. An example of a PBIB(<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667061.png" />)-design is a block design which may be represented as the table

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667062.png" /></td> </tr></table>

where any two numbers in the same column are <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667063.png" />-associated, while any two numbers in different columns are <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667064.png" />-associated. Here <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667065.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667066.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667067.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667068.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667069.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667070.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667071.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667072.png" />.

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667073.png" /></td> </tr></table>

To each block design with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667074.png" /> elements and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667075.png" /> blocks corresponds an incidence matrix <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667076.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667077.png" /> if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667078.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667079.png" /> otherwise, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667080.png" />; <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667081.png" />. 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:

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667082.png" /></td> <td valign="top" style="width:5%;text-align:right;">(1)</td></tr></table>

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667083.png" /></td> </tr></table>

Equation (1) and the relationships

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667084.png" /></td> </tr></table>

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667085.png" /></td> </tr></table>

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667086.png" /></td> </tr></table>

are valid for the parameters of PBIB(<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667087.png" />)-designs. The incidence matrix of a BIB-design satisfies the fundamental matrix relation

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667088.png" /></td> <td valign="top" style="width:5%;text-align:right;">(2)</td></tr></table>

where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667089.png" /> is the unit matrix of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667090.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667091.png" /> is the matrix of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667092.png" /> consisting exclusively of ones. The existence of a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667093.png" />-matrix which satisfies condition (2) is a sufficient condition for the existence of a BIB-design with the given parameters. The [[Fisher inequality]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667094.png" /> follows from (2). A BIB-design for which <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667095.png" /> (i.e. also <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667096.png" />) is said to be a symmetric block design or a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667098.png" />-configuration. The following theorem applies to symmetric BIB-designs: If there exists a symmetric BIB-design with parameters <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b01667099.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b016670100.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b016670101.png" />, then: 1) if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b016670102.png" /> is even, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b016670103.png" /> is a perfect square; 2) if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b016670104.png" /> is odd, the equation

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b016670105.png" /></td> </tr></table>

has a solution in integers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b016670106.png" />, not all of which are zero. The conditions of this theorem are sufficient for the existence of a rational matrix <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b016670107.png" /> satisfying equation (2).

A special range of problems involving the existence of BIB-designs arises in the context of the following problem: Given <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b016670108.png" /> 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b016670109.png" />, as well as the possibility of representing <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b016670110.png" /> 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b016670111.png" />), in particular Steiner triple systems (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b016670112.png" />); Hadamard configurations (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b016670113.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b016670114.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b016670115.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b016670116.png" />), the incidence matrix of which is obtained from a [[Hadamard matrix|Hadamard matrix]]; affine finite geometries and projective finite geometries [[#References|[1]]]. In the class of PBIB-designs those most extensively studied are PBIB(<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b016670117.png" />)-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. [[#References|[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====
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  H.J. Ryser,   "Combinatorial mathematics" , Wiley  (1963)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  M. Hall,   "Combinatorial theory" , Blaisdell  (1967)</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  S.A. Shirokova,   "Block designs"  ''Russian Math. Surveys'' , '''23''' :  5  (1968)  pp. 47–94  ''Uspekhi Mat. Nauk'' , '''23''' :  5  (1968)  pp. 51–98</TD></TR></table>



====Comments====
The theorem giving conditions on the numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016670/b016670118.png" /> in order that a symmetric BIB-design with these numbers as parameters exists, is called the Bruck–Ryser–Chowla theorem.

[[Category:Combinatorics]]