Block design

A block diagram ( also block design or combinatorial design) is a finite incidence structure that is particular in finite geometry, combinatorics and statistical design of experiments is important. Block diagrams are a common generalization of the finite affine planes and the finite projective planes.

Important methods for the characterization of block diagrams, and construction of new block designs from well-known are the resolution and the tactical decomposition of a block plan. The resolution generalizes the concept of parallelism of a block plan, as this article describes, and is itself a special case of the tactical decomposition.

• 6.1 Non- existing simple 2- block plans
• 6.2 Existing simple t- block designs with t ≥ 4

Definitions and notations

Be a finite incidence structure in which the elements of the points of the elements are referred to as blocks. Furthermore, are natural numbers, then the incidence structure is called a block plan if the following axioms hold:

• (B1 ) has exactly points, ie,
• (B2 ) of each block is incident with exactly points, ie,
• (B3 ) for each set of points with different points exist just several blocks, and each of G incident with all the points, so
• (B4), that is, is a non- degenerate incidence structure.

An alternative term for a block plan will also be used. In the case of one writes simply and speaks of a Steiner system ( after Jakob Steiner). A block diagram ( ) is also called a Steiner triple system. Partial block design is also used as written, the additional parameters will be discussed below.

A block diagram is often referred to briefly also block plan and a block plan simply as a block diagram, since the case is most commonly used.

The constant number of all blocks through a point of is denoted by and the number of all blocks with.

Based on specific geometric models for a block plan its blocks are sometimes referred to as lines, circles, planes, or the like. If a point is incident with a block, ie, including the follow ways of speaking are common: lying on or passing through. Incised with a point several blocks, so we can also say that the blocks intersect in.

Block plans for which a block with all the points incised, or in which the subsets of the set of points exactly correspond to the blocks are called trivial block plans.

A block must be formally distinguished from the inzidierenden with him point set, but it is in practice usually possible to identify a block with his inzidierenden point set and interpret the incidence relation as a set-theoretic containment. Such block designs are also referred to as simply (see the examples in the article " Incidence structure").

Properties

For the number of blocks of a block plan applies:

With for you is the number of blocks the incident with all points of any set of points with points, so this applies to:

For block diagrams obtained from the two formulas taking into account:

Moreover, for the block plans Fisher's inequality:

In addition to the mentioned in the examples below, finite projective and affine spaces are block plans in exchange relationships with many other structures in combinatorics. For example, the existence of a block plan with equivalent to the existence of a Hadamard matrix of order. For this reason such block diagrams are also called Hadamard block plans. The relationship between codes and block diagrams describes the set of Assmus - Mattson.

A central question in the theory of block designs is for what values ​​of the parameters exists at all is a block diagram. While a general answer to this question is still pending, there is after a result of Teirlinck L. (1987 ) but for every one non-trivial t- block plan. In addition, there are a number of criteria necessary for the existence of certain block designs, with which one can exclude many parameter combinations. Such criteria are, for example, the generalized Fisher's inequality (also set by Ray - Chaudhuri -Wilson called ) and the set of Bruck- Ryser- Chowla.

Balanced block designs

A block plan, which has just as many blocks as points is referred to as symmetric or projective. Balanced block designs can be characterized under the 2- block plans by various equivalent statements: Be a block plan is the total number of its blocks and is an incidence matrix of this block diagram. Then the following statements are equivalent:

The interval in which the number of dots (or blocks) varies with respect to the order of a symmetrical block plan, are calculated as if a non-trivial Bloclplan present with. The lower Extremalfall is given for Hadamard block plans and the upper Extremalfall for finite projective planes.

Parallelisms and affine block plans

A parallelism of a block plan is an equivalence relation on the set of blocks for which the Euclidean parallel postulate holds:

These blocks are called parallel ( spelling) when they are in the same equivalence class. The equivalence classes themselves are also called parallel classes or parallel droves. For two parallel blocks that they ( or more accurately the inzidierenden with them point sets ) are either identical or disjoint:

A parallelism of a block plan, always have the same number of points in which any two non-parallel blocks together is, affine and the corresponding block diagram is called affine block diagram. While generally a block plan may permit more parallelism, the parallelism is uniquely determined in a block affine plan and it is also the reverse of the above relation:

For block designs with parallelism of the set of Bose, which represents a tightening of Fisher's inequality for this case applies.

Examples

The Wittschen block diagrams ( in the narrow sense ) are simple 5 block plans, their derivatives, which are often referred to as Witt block plans provide examples of non-trivial simple 4 - and 3- block plans.

Affine geometries as block plans

The affine space of dimension over the finite field with elements is as quoted. He becomes a block diagram by using the set of points of the affine space as a set of points and the - dimensional affine subspaces as blocks. More precisely, in a block diagram. The usual parallelism of the affine geometry is a parallelism for the block diagram and the block diagram is thus exactly then to a block affine plan if valid, so the blocks are hyperplanes of the space. The parameters of the block plan are:

Here is the Gaussian binomial coefficients, the formula by the

Can be calculated for. The rooms are even 3 - block plans. Specifically, an affine block diagram with its geometric parallelism.

Projective geometries as block plans

The projective space of dimension over the finite field is as quoted. The block plan has as point set the set of projective points and a block amount the amount of the - dimensional projective subspaces of. This is a block diagram with the parameters

In case, therefore, if the blocks are the hyperplanes of the space, the block diagram is symmetrical.

Illustrative examples

As special cases of the above-mentioned classic geometric spaces can be a finite projective plane of order as a block plan and a finite affine plane of order regarded as a block diagram. These correspond to the points of the plane the points of the block plan and the straight lines of the plane the blocks of the block diagram. However, the existence of the appropriate level of order is required and this is not the case for everyone.

Small planes, see also the diagrams at the end of the section:

• The projective plane of order 2 ( the Fano plane ) is a symmetric block plan at the same time it is "the" smallest Hadamard block diagram.
• The affine planes of orders 2 and 3 and, together with its ordinary and only possible parallelism an affine block diagram or block diagram.

Other (counter ) examples of simple block plans

Not existing simple 2- block plans

For appearing in the following list Parametertripel (in the range, there are no simple block diagrams, although the usual parameter conditions are met:

Existing simple t- block designs with t ≥ 4

Concrete examples of simple block plans were long known only sporadically.

For example:

Until the 1980's even years it was unclear whether ( approximately ) simple block diagrams occur at all. Then gradually, several examples were found:

In recent years, with the help of more sophisticated group-theoretic, geometric and computer-assisted methods eventually even a number of simple block with plans been found; including the following: