Combinatorics of optimal design

To a combinatorialist, a design is usually a 2-design or balanced incomplete-block design. However, 2-designs do not necessarily exist in all cases where astatistician might wish to use one to design an experiment. As a result, statisticians need to consider structures much more general than the combinatorialist’s designs, and to decide which one is “best” in a given situation. This leads to the theory of optimal design. There are several concepts of optimality, and no general consensus about which one to use in any particular situation.For block designs with fixed block size k, all these optimality criteria aredetermined by a graph, the concurrence graph of the design, and more specifically, by the eigenvalues of the Laplacian matrix of the graph. It turns out that the optimality criteria most used by statisticians correspond to properties of this graph which are interesting in other contexts: D-optimality involves maximizing the number of spanning trees; A-optimality involves minimizing the sum of resistances between all pairs of terminals (when the graph is regarded as an electrical circuit, with each edge being a one-ohm resistor); and E-optimality involves maximizing the smallest eigenvalue of the Laplacian (the corresponding graphs are likely to have good expansion and random walk properties). If you are familiar with these properties, you may expect that related “nice” properties such as regularity and large girth (or even symmetry) may tend to hold; some of our examples may come as a surprise!The aim of this paper is to point out that the optimal design point of viewunifies various topics in graph theory and design theory, and suggests someinteresting open problems to which combinatorialists of all kinds might turntheir expertise. We describe in some detail both the statistical background andthe mathematics of various topics such as Laplace eigenvalues of graphs