Block Design - Definition of A BIBD (or 2-design)

Definition of A BIBD (or 2-design)

Given a finite set X (of elements called points) and integers k, r, λ ≥ 1, we define a 2-design (or BIBD, standing for balanced incomplete block design) B to be a family of k-element subsets of X, called blocks, such that the number r of blocks containing x in X is not dependent on which x is chosen, and the number λ of blocks containing given distinct points x and y in X is also independent of the choices.

"Family" in the above definition can be replaced by "set" if repeated blocks are not allowed. Designs in which repeated blocks are not allowed are called simple.

Here v (the number of elements of X, called points), b (the number of blocks), k, r, and λ are the parameters of the design. (To avoid degenerate examples, it is also assumed that v > k, so that no block contains all the elements of the set. This is the meaning of "incomplete" in the name of these designs.) In a table:

v	points, number of elements of X
b	blocks
r	number of blocks containing a given point
k	number of points in a block
λ	number of blocks containing 2 (or more generally t) points

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

These conditions are not sufficient as, for example, a (43,7,1)-design does not exist.

The order of a 2-design is defined to be n = r − λ. The complement of a 2-design is obtained by replacing each block with its complement in the point set X. It is also a 2-design and has parameters v′ = v, b′ = b, r′ = b−r, k′ = v−k, λ′ = λ+b−2r. A 2-design and its complement have the same order.

A fundamental theorem, Fisher's inequality, named after the statistician Ronald Fisher, is that b ≥ v in any 2-design.