Introduction#

Since there is some variation between authors of the terminology employed in design theory, we begin with some definitions. An incidence structure is a triple \(D = (P, B, I)\), where:

(a): \(P\) is a set, the elements of which are called points;
(b): \(B\) is a set, the elements of which are called blocks;
(c): \(I\) is an incidence relation between \(P\) and \(B\), so that \(I \subset P \times B\). The elements of \(I\) are called flags.

Usually, blocks will be subsets of \(P\), so that instead of writing \((p, b) \in I\), we write \(p \in b\). In general, repeated blocks are allowed so that different blocks may correspond to the same subset of \(P\). If \(D\) has no repeated blocks, then we say that \(D\) is simple.

An incidence structure \(D\) is said to be uniform with blocksize \(k\) if \(D\) has at least one block and all blocks contain exactly \(k\) points. A uniform incidence structure is called trivial if each \(k\)-subset of the point set appears as a block (at least once).

Let \(t \ge 0\) be an integer. Then an incidence structure \(D\) is said to be \(t\)–balanced if there exists an integer \(\lambda \ge 1\) such that each \(t\)–subset of the point set is contained in exactly \(\lambda\) blocks of \(D\).

A near–linear space is an incidence structure in which every block contains at least two points and any two points lie in at most one block. A linear space is a near–linear space in which any two points lie in exactly one block. It is usual, when discussing near–linear spaces, to use the term line in place of the term block.

Let \(v\), \(k\), \(t\) and \(\lambda\) be integers with \(v \ge k \ge t \ge 0\) and \(\lambda \ge 1\). A \(t\)–design with \(v\) points and blocksize \(k\) is an incidence structure \(D = (P, B, I)\) where:

(a): The cardinality of \(P\) is \(v\);
(b): \(D\) is uniform with blocksize \(k\);
(c): \(D\) is simple;
(d): For each \(t\)–subset \(T\) of \(P\) there are exactly \(\lambda\) blocks of \(B\) incident with all the points of \(T\) (so \(D\) is \(t\)–balanced).

Such a design is usually referred to as a \(t\)–\((v,k,\lambda)\) design. The parameter \(\lambda\) is called the index of the design. If \(b\) denotes the cardinality of \(B\), a \(t\)–design with \(v = b\) and \(t \ge 2\) is called a symmetric design. A \(t\)–design with \(\lambda = 1\) is called a Steiner design. A design which is trivial is also called a complete design. Note that a design \(D\) must contain at least one block (i.e \(b > 0\)).

The category names for the different families of incidence structures are as follows:

Incidence structure : Inc
Near-linear space : IncNsp
Linear space : IncLsp
\(t\)–design : Dsgn