E    
  D  
    T

Encyclopaedia of DesignTheory: t-Designs

General Partition Incidence Array
Experimental Other designs Math properties Stat properties
Server External Bibliography Miscellaneous

Topic essays:

t-Designs

Definition

A t-(v, k, lambda) design, or (for short) a t-design, is an incidence structure of points and blocks with the following properties: Here t, v, k, lambda are non-negative integers.

Some non-degeneracy conditions are usually assumed, though there is no agreement about exactly what these should be. It is reasonable to assume that t<=k<=v. With this condition, if lambda=0, there are no blocks at all, so we usually assume that lambda>0. Now if t=k, then each set of k points occurs the same number of times as a block; while if k=v, then every block is incident with every point. These designs are not very interesting, so it is often assumed that t<k<v.

A t-design with lambda=1 is called a Steiner system. In particular, a 2-(v,3,1) design is a Steiner triple system or STS, and a 3-(v,4,1) design is a Steiner quadruple system or SQS. On the Steiner triple system page, you can see an example of a 2-(7,3,1) design.

A 2-design with k<v is also referred to as a balanced incomplete-block design or BIBD.

A t-design is said to have repeated blocks if there are two blocks incident with the same set of k points. A design with no repeated blocks is said to be simple. Thus, in a simple design, we can identify each block with the set of points incident with it.

Existence

The collection of all k-subsets of a v-set forms a simple t-design for all t<k. It is relatively easy to show that, for any given t, k, v with t<k<v-t there exists a t-(v, k, lambda) design in which not every k-set is incident with a block, for some value of lambda.

However, the existence of simple t-designs in which not every k-set is a block is a much more difficult question, and was only settled affirmatively by Teirlinck in 1987. Teirlinck's designs have k = t+1, and the values of lambda and v are quite large.

One of the most important and difficult questions in design theory is:

For which values of t, k, v with t<k<v does a t-(v,k,1) Steiner system exist? In particular, do such designs exist for arbitrarily large values of t?
At present, the largest value of t for which Steiner systems are known to exist is t=5.

Table of contents | Glossary | Topics | Bibliography | History

Peter J. Cameron
4 October 2004