design

A $\tau$-$(\nu ,\kappa ,\lambda )$ design, aka $\tau$-design or block design, is an incidence structure $(𝒫,ℬ,ℐ)$ with

• $|𝒫|=\nu$ points in all,

• $|{𝒫}_B|=\kappa$ points in each block $B$, and such that

• any set $T\subseteq 𝒫$ of $|T|=\tau$ points occurs as subset $T\subseteq {𝒫}_B$ in exactly $\lambda$ blocks.

The numbers $\tau ,\nu ,\kappa ,lambda$ are called the parameters of a design. They are often called $t$, $v$, $k$, $\lambda$ (in mixed Latin and Greek alphabets) by some authors.

Given parameters $\tau ,\nu ,\kappa ,lambda$, there may be several non-isomorphic designs, or no designs at all.

Designs need not be simple (they can have repeated blocks), but they usually are (and don’t) in which case $B$ can again be used as synonym for ${𝒫}_B$.

• 0-designs ($\tau =0$) are allowed.

• 1-designs ($\tau =1$) are known as tactical configurations.

• 2-designs are called balanced incomplete block designs or BIBD.

• 3, 4, 5… -designs have all been studied.

Being a $\tau$-$(\nu ,\kappa ,\lambda )$ design implies also being an $\iota$-$(\nu ,\kappa ,{\lambda }_{\iota })$ design for every $0\le \iota \le \tau$ (on the same $\nu$ points and with the same block size $\kappa$), with ${\lambda }_{\iota }$ given by ${\lambda }_{\tau }=\lambda$ and recursively

$${\lambda }_{\iota }=\frac{\nu -\iota }{\kappa -\iota }{\lambda }_{\iota +1}$$

from which we get the number of blocks as

$${\lambda }_0=\frac{\nu !/(\nu -\tau )!}{\kappa !/(\kappa -\tau )!}=\left(\genfrac{}{}{0pt}{}{\nu }{\tau }\right)/\left(\genfrac{}{}{0pt}{}{\kappa }{\tau }\right)$$

Being a 0-design says nothing more than all blocks having the same size. As soon as we have $\tau \ge 1$ however we also have a 1-design, so the number ${\lambda }_1=|{ℬ}_P|$ of blocks per point $P$ is constant throughout the structure. Note now

$${\lambda }_0\kappa ={\lambda }_1\nu$$

which is also evident from their interpretation.

As an example: designs (simple designs) with $\kappa =2$ are multigraphs (simple graphs), now

• $\tau =0$ implies no more than that,

• $\tau =1$ gives regular graphs, and

• $\tau =2$ gives complete graphs.

A more elaborate “lambda calculus” (pun intended) can be introduced as follows. Let $I\subseteq P$ and $O\subseteq P$ with $|I|=\iota$ and $|O|=o$. The number of blocks $B$ such that all the points of $I$ are inside $B$ and all the points of $O$ are outside $B$ is independent of the choice of $I$ and $O$, only depending on $\iota$ and $o$, provided $\iota +o\le \tau$. Call this number ${\lambda }_{\iota }^o$. It satisfies a kind of reverse Pascal triangle like recursion

$${\lambda }_{\iota }^o={\lambda }_{\iota +1}^o+{\lambda }_{\iota }^{o+1}$$

that starts off for $o=0$ with ${\lambda }_{\iota }^0={\lambda }_{\iota }$. An important quantity (for designs with $\tau \ge 2$) is the order ${\lambda }_1^1={\lambda }_1^0-{\lambda }_2^0={\lambda }_1-{\lambda }_2$.

Finally, the dual of a design can be a design but need not be.

• A square design aka symmetric design is one where $\tau =2$ and $|𝒫|=|ℬ|$, now also $|{𝒫}_B|=|{ℬ}_P|$. Here the dual is also a square design.

Note that for $\tau \ge 3$ no designs exist with $|𝒫|=|ℬ|$ other than trivial ones (where any $\kappa =\nu -1$ points form a block).

Title	design
Canonical name	Design
Date of creation	2013-03-22 19:14:09
Last modified on	2013-03-22 19:14:09
Owner	CWoo (3771)
Last modified by	CWoo (3771)
Numerical id	5
Author	CWoo (3771)
Entry type	Definition
Classification	msc 62K10
Classification	msc 51E30
Classification	msc 51E05
Classification	msc 05B25
Classification	msc 05B07
Classification	msc 05B05
Synonym	block design
Synonym	tau-design
Synonym	$\tau$-design
Synonym	BIBD
Defines	block
Defines	simple design
Defines	square design
Defines	symmetric design
Defines	tactical configuration
Defines	balanced incomplete block design