Some Advances in Computational Design Theory

Brendan D. McKay

Department of Computer Science Australian National University, Canberra

Abstract

A design is simply a collection of subsets (called “blocks”) of a set, or equivalently a hypergraph. The name derives from the use of certain types of designs to arrange scientific experiments in a way that allows easy analysis of the results. One of the most important classes of designs are the so-called balanced incomplete block designs (BIBDs). These have four parameters, t−(v, k, λ), indicating that the underlying set has v points, each block has k points, and each set of t points is contained in exactly λ blocks.

The talk will focus on the following two related aspects of computational design theory: isomorphism testing and generation.

The problems of computing automorphism groups and testing isomorphism are closely related. We will describe an approach based on nested partitions of the point set.

An “orderly” generation algorithm for a class of designs is one that produces just one representative of each isomorphism type without the need to store and compare many designs. We will describe an approach that is quite successful for small designs.

Finally, we mention two difficult existence problems, attacked jointly with Stanisław Radziszowski. Firstly, the 4-(12,6,6) design does not exist. Secondly, the 2-(22,8,4) design doesn’t exist either, if only we could prove it.

Refreshments and cookies will be served