The Full Wiki

Block design: Wikis

Advertisements
  

Note: Many of our articles have direct quotes from sources you can cite, within the Wikipedia article! This article doesn't yet, but we're working on it! See more info or our list of citable articles.

Encyclopedia

From Wikipedia, the free encyclopedia

In combinatorial mathematics, a block design is a particular kind of set system, which has applications to experimental design, finite geometry, software testing, cryptography, and algebraic geometry. Many variations have been studied, including balanced incomplete block designs.[1][2]

Given a finite set X (of elements called points) and integers k, r, λ ≥ 1, we define a 2-design B to be a set of k-element subsets of X, called blocks, such that the number r of blocks containing x in X is independent of x, and the number λ of blocks containing given distinct points x and y in X is also independent of the choices.

Here v (the number of elements of X, called points), b (the number of blocks), k, r, and λ are the parameters of the design. (Also, B may not consist of all k-element subsets of X; that is the meaning of incomplete.) The design is called a (v, k, λ)-design or a (v, b, r, k, λ)-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

 bk = vr, \,
 \lambda(v-1) = r(k-1). \,

These conditions are not sufficient as for example a (43,7,1)-design does not exist. A fundamental theorem, Fisher's inequality, named after Ronald Fisher, is that bv in any block design. The case of equality is called a symmetric design; it has many special features.

Examples of block designs include the lines in finite projective planes (where X is the set of points of the plane and λ = 1), and Steiner triple systems (k = 3 and λ = 1). The former is a relatively simple example of a symmetric design. Triple systems (k = 3) are of interest in their own right.[3]

Contents

Projective planes

Projective planes are a special case of block designs, where we have \scriptstyle v \,>\, 0 points and, as they are symmetric designs, \scriptstyle b \,=\, v (which is the limit case of Fisher's inequality), from the first basic equation we get

k = r, \,

and since \scriptstyle \lambda \,=\, 1 by definition, the second equation gives us

v-1 = k(k-1).\,

Now, given an integer \scriptstyle n \,\geq\, 1, called the order of the projective plane, we can put k = n + 1 and, from the displayed equation above, we have \scriptstyle v \,=\, (n+1)n \,+\, 1 \,=\, n^2 \,+\, n \,+\, 1 points in a projective plane of order n.

Since a projective plane is symmetric, we have that \scriptstyle b \,=\, v, which means that \scriptstyle b \,=\, n^2 \,+\, n \,+\, 1 also. The number b is usually called the number of lines of the projective plane.

This means, as a corollary, that in a projective plane, the number of lines and the number of points are always the same. For a projective plane, k is the number of lines and it is equal to n + 1, where n is the order of the plane. Similarly, r = n + 1 is the number of lines to which the 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.

Generalization: t-designs

Given any integer t ≥ 2, a t-design B is a class of k-element subsets of X (the set of points), called blocks, such that every point x in X appears in exactly r blocks, and every t-element subset T appears in exactly λ blocks. The numbers v (the number of elements of X), b (the number of blocks), k, r, λ, and t are the parameters of the design. The design may be called a t-(v,k,λ)-design. Again, these four numbers determine b and r and the four numbers themselves cannot be chosen arbitrarily. The equations are

 b_i = \lambda \left.\binom{v-i}{t-i} \right/ \binom{k-i}{t-i} \text{ for } i = 0,1,\ldots,t,

where bi is the number of blocks that contain any i-element set of points.

There are no known examples of non-trivial t-(v,k,1)-designs with \scriptstyle t >\, 5.

The term block design by itself usually means a 2-design.

See also

Notes

  1. ^ Handbook of combinatorial designs. Edited by Charles J. Colbourn and Jeffrey H. Dinitz. Second edition. Discrete Mathematics and its Applications (Boca Raton). Chapman & Hall/CRC, Boca Raton, FL, 2007
  2. ^ Stinson, Douglas R. Combinatorial designs: Constructions and analysis. Springer-Verlag, New York, 2004. xvi+300 pp. ISBN 0-387-95487-2
  3. ^ Colbourn, Charles J. and Rosa, Alexander, Triple systems, Oxford Mathematical Monographs,The Clarendon Press Oxford University Press, New York.1999,ISBN 0-19-853576-7

References

External links

  • Design DB: A database of combinatorial, statistical, experimental block designs
Advertisements

Advertisements






Got something to say? Make a comment.
Your name
Your email address
Message