Intensive course on
Laplacian eigenvalues and optimality
Lecturers: R. A. Bailey and Peter J. Cameron (QMUL)
Rockefeller Building, Gower Street, London
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:
office@ltcc.ac.uk
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
