Block design

From Wikipedia, the free encyclopedia

For an account of the concept in intelligence testing, see block design test.

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 b ≥ v 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]

[edit] 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.

[edit] 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 the number r of blocks that contain any point x in X is independent of x, and the number λ of blocks that contain any given t-element subset T is independent of the choice of T. 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 b_i 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.

[edit] See also

Randomized block design

[edit] External links

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

[edit] References

^ 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
^ Stinson, Douglas R. Combinatorial designs: Constructions and analysis. Springer-Verlag, New York, 2004. xvi+300 pp. ISBN 0-387-95487-2
^ 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

van Lint, J.H., and R.M. Wilson (1992), A Course in Combinatorics. Cambridge, Eng.: Cambridge University Press.
S. S. Shrikhande, and Vasanti N. Bhat-Nayak, Non-isomorphic solutions of some balanced incomplete block designs I – Journal of Combinatorial Theory, 1970
Raghavarao, Damaraju (1988). Constructions and Combinatorial Problems in Design of Experiments (corrected reprint of the 1971 Wiley ed.). New York: Dover.
Raghavarao, Damaraju and Padgett, L.V. (2005). Block Designs: Analysis, Combinatorics and Applications. World Scientific.
Street, Anne Penfold and Street, Deborah J. (1987). Combinatorics of Experimental Design. Oxford U. P. [Clarendon]. pp. 400+xiv. ISBN 0198532563.

Weistein, Eric W., "Block Designs" from MathWorld.

[0] 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

[1] Stinson, Douglas R. Combinatorial designs: Constructions and analysis. Springer-Verlag, New York, 2004. xvi+300 pp. ISBN 0-387-95487-2

[2] 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

[1]

[2]

[3]

Block design

From Wikipedia, the free encyclopedia

Contents

[edit] Projective planes

[edit] Generalization: t-designs

[edit] See also

[edit] External links

[edit] References

Views

Personal tools

Navigation

Search

Interaction

Toolbox

Languages