Difference between revisions of "Block design"
(typo) |
(Category:Combintorics) |
||
Line 66: | Line 66: | ||
====Comments==== | ====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. | 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:Combintorics]] |
Revision as of 19:41, 9 November 2014
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 where
![]() |
![]() |
The elements of the set are called the points (treatments) of the block design, or varieties or elements, while the elements of the set
are called its blocks. The element
and the block
are incident if
. The number
of elements incident with
is usually denoted by
, while the number of blocks incident with
is denoted by
. The number
![]() |
is denoted by . The numbers
,
,
(
;
) are said to be the parameters of the block design. If
for all
,
for all
and
,
is a balanced incomplete block design (BIB-design) with parameters
,
,
,
,
. 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
-element sets are included in
.
Let exactly different numbers
be encountered among the numbers
,
, and let
symmetric association relations be introduced on the elements of the set
so that the following conditions are satisfied:
1) the set of all pairs of distinct elements of
is subdivided into
disjoint subsets
and, if
, then
and
are said to be
-associated;
2) ,
,
;
3) ,
;
4) , and, in view of the symmetry,
,
. A block design with the properties 1)–4) is said to be a partial balanced incomplete block design with
types of relations or a PBIB(
)-design. The rule which specifies the association relation is called the association design. A BIB-design is a PBIB(
)-design. An example of a PBIB(
)-design is a block design which may be represented as the table
![]() |
where any two numbers in the same column are -associated, while any two numbers in different columns are
-associated. Here
,
,
,
,
,
,
,
.
![]() |
To each block design with elements and
blocks corresponds an incidence matrix
, where
if
and
otherwise,
;
. 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:
![]() | (1) |
![]() |
Equation (1) and the relationships
![]() |
![]() |
![]() |
are valid for the parameters of PBIB()-designs. The incidence matrix of a BIB-design satisfies the fundamental matrix relation
![]() | (2) |
where is the unit matrix of order
and
is the matrix of order
consisting exclusively of ones. The existence of a
-matrix which satisfies condition (2) is a sufficient condition for the existence of a BIB-design with the given parameters. The inequality
follows from (2). A BIB-design for which
(i.e. also
) is said to be a symmetric block design or a
-configuration. The following theorem applies to symmetric BIB-designs: If there exists a symmetric BIB-design with parameters
,
,
, then: 1) if
is even,
is a perfect square; 2) if
is odd, the equation
![]() |
has a solution in integers , not all of which are zero. The conditions of this theorem are sufficient for the existence of a rational matrix
satisfying equation (2).
A special range of problems involving the existence of BIB-designs arises in the context of the following problem: Given 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
, as well as the possibility of representing
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 ), in particular Steiner triple systems (
); Hadamard configurations (
,
,
,
), 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(
)-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 in order that a symmetric BIB-design with these numbers as parameters exists, is called the Bruck–Ryser–Chowla theorem.
Block design. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Block_design&oldid=34449