Combinatorics of optimal design

Research output: Chapter in Book/Report/Conference proceedingChapter (peer-reviewed)


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 a
statistician 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 are
determined 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 view
unifies various topics in graph theory and design theory, and suggests some
interesting open problems to which combinatorialists of all kinds might turn
their expertise. We describe in some detail both the statistical background and
the mathematics of various topics such as Laplace eigenvalues of graphs.
Original languageEnglish
Title of host publicationSurveys in Combinatorics 2009
EditorsS. Huczynska, J. D. Mitchell, C. M. Roney-Dougal
Place of PublicationCambridge
PublisherCambridge University Press
Number of pages55
ISBN (Print)978-0-521-74173-6
Publication statusPublished - 2009

Publication series

NameLondon Mathematical Society Lecture Notes


Dive into the research topics of 'Combinatorics of optimal design'. Together they form a unique fingerprint.

Cite this