Abstract
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.
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 language | English |
|---|---|
| Title of host publication | Surveys in Combinatorics 2009 |
| Editors | S. Huczynska, J. D. Mitchell, C. M. Roney-Dougal |
| Place of Publication | Cambridge |
| Publisher | Cambridge University Press |
| Pages | 19-73 |
| Number of pages | 55 |
| ISBN (Print) | 978-0-521-74173-6 |
| Publication status | Published - 2009 |
Publication series
| Name | London Mathematical Society Lecture Notes |
|---|---|
| Volume | 365 |