Laplacian eigenvalues and optimality
Lecturers: R. A. Bailey and Peter J. Cameron (QMUL)
13–14 June 2012, UCL
- 13 June: 1pm - 5pm, Room 337 David Sachs, Rockefeller Building, University Street
- 14 June: 9am - 1pm, Room G02, Rockefeller Building
Eigenvalues of the Laplacian matrix of a graph have been widely used in studying connectivity and expansion properties of networks.
Independently, statisticians introduced various optimality criteria in experimental design, the goal being to obtain more accurate estimates of quantities of interest in an experiment. It turns out that the most popular of these optimality criteria for block designs are determined by the Laplacian eigenvalues of the concurrence graph, or the Levi graph, of the design.
The most important optimality criteria, called A (average), D (determinant) and E (extreme), are related to the conductance of the graph as an electrical network, the number of spanning trees, and the isoperimetric properties of the graphs.
The number of spanning trees is also an evaluation of the Tutte polynomial of the graph, and is the subject of the Merino--Welsh conjecture relating it to acyclic and totally cyclic orientations, of interest in their own right.
Note to students and others intending to attend the course:
We intend to make the course self-contained as far as possible. However, you may wish to do some preliminary reading before the course. We recommend the following:
- R. A. Bailey and Peter J. Cameron, Combinatorics of optimal designs. In Surveys in Combinatorics 2009 (ed. S. Huczynska, J. D. Mitchell and C. M. Roney-Dougal), London Math. Soc. Lecture Notes 365, Cambridge University Press 2009, pp. 19–73.
- R. A. Bailey and Peter J. Cameron, Using graphs to find the best block designs, arXiv 1111.3768.
- B. Bollobás, Modern Graph Theory. Graduate Texts in Mathematics 184, Springer, New York, 1998, Chapters II and IX.
For further details download the PDF abstract: