Algorithmic aspects of integral designs

Abstract

A t-design with parameters t - (v, k, λ.) is a set X of cardinality v, together with a collection of subsets of X of size k called blocks. The number of blocks containing any particular t-subset of X is a constant λ. The simplest t-designs are regular multi-graphs (t=1, k=2, v= number of vertices, λ = degree of regularity). Necessary conditions on the four parameters for the existence of t-designs are simply obtained by counting the number of blocks containing a particular i-subset of X for any 0 ≤ i ≤ t. In general these necessary conditions are not sufficient for the existence of t-designs. However these simple counting conditions are sufficient for the existence of so-called "integral designs" which are an extension of the definition of t-designs, allowing blocks to have negative as well as non-negative multiplicities. The sufficiency of the elementary necessary conditions for the existence of integral designs was proved independently by Graver andJurkat, and Wilson in the early 1970s. The proof by Wilson is algorithmic in nature. We discuss implementations of his construction algorithm which aim to both reduce the number of blocks with negative multiplicities, and also reduce the absolute value of the most negative multiplicity - thus hoping to produce integral designs which are "close" to designs.