Laplacian eigenvalues and optimality

Lecturers: R. A. Bailey and Peter J. Cameron (QMUL)

13–14 June 2012

A request |
---|

If you were at the lectures on Wednesday afternoon, and didn't get your name on the attendance sheet, could you please email Nisha Jones (address below). It is helpful to the LTCC to have accurate data! Thank you for your consideration. |

Registration | Synopsis | Course materials | Other materials

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.

The course is over now. But here is Nisha Jones' email for correspondence about technical aspects of the course:

For mathematical aspects, email one of the lecturers: R.A.Bailey or P.J.Cameron at qmul.ac.uk.

Details of all LTCC intensives are available here.

The course was organised as four 2-hour lectures, commencing at 1pm on Wednesday 13 June 2012, and finishing at around 1pm the next day.

- Lecture 1: Block designs (RAB)
- Block designs in use; complete- and incomplete-block designs; balanced incomplete-block designs; estimation using block designs.
- Lecture 2: Graphs and Laplacians (PJC)
- The Laplacian matrix of a graph and its spectrum; connections with spanning trees, isoperimetric properties, electrical networks and random walks.
- Lecture 3: Designs, graphs and optimality (RAB)
- The concurrence and Levi graphs of a block design. Variance and resistance, spanning trees. Definitions of optimality; optimality of BIBDs and group divisible designs.
- Lecture 4: More on graphs (PJC)
- Optimality and graph properties; variance-balanced designs. The Tutte polynomial; spanning trees, acyclic and totally cyclic orientations of graphs.

The lecture slides have been updated since the lectures were given. Current versions from 15 June.

Here is some recommended further reading.

- 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.
- Bela Bollobás,
*Modern Graph Theory*. Graduate Texts in Mathematics**184**, Springer, New York, 1998, Chapters II and IX. - Guiliana Davidoff, Peter Sarnak and Alain Valette,
*Elementary Number Theory, Group Theory and Ramanujan Graphs*, London Math. Soc. Student Texts**55**, Cambridge University Press, 2003. - B. Mohar,
Some applications of Laplace eigenvalues of graphs,
in
*Graph Symmetry: Algebraic Methods and Applications*(ed. G. Hahn and G. Sabidussi), NATO ASI Series C, Kluwer, 1997, pp.227-276. - A. D. Sokal,
The multivariate Tutte polynomial (alias Potts model) for graphs and matroids,
*Surveys in combinatorics 2005*(ed. B. S. Webb), pp.173-226, London Math. Soc. Lecture Note Series**327**, Cambridge Univ. Press, Cambridge, 2005.

Peter J. Cameron

15 June 2012