3 - Laplacian eigenvalues and optimality
Published online by Cambridge University Press: 11 May 2024
Summary
Eigenvalues of the Laplacian matrix of a graph have been widely used in studying connectivity and expansion properties of networks, and also in analyzing random walks on a graph. 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 of 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, respectively. 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. This chapter ties these ideas together, building on the work in [4] and [5].
- Type
- Chapter
- Information
- Groups and Graphs, Designs and Dynamics , pp. 176 - 265Publisher: Cambridge University PressPrint publication year: 2024
References
Bailey, R. A., Association Schemes: Designed Experiments, Algebra and Combinatorics. Cambridge University Press, Cambridge, 2004.CrossRefGoogle Scholar
Bailey, R. A., Design of Comparative Experiments. Cambridge University Press, Cambridge, 2008.CrossRefGoogle Scholar
Bailey, R. A., Variance and concurrence in block designs, and distance in the corresponding graphs, Michigan Mathematical Journal 58 (2009), 105–124.CrossRefGoogle Scholar
Bailey, R. A. and Cameron, Peter J., Combinatorics of optimal designs. In Surveys in Combinatorics 2009 (eds. Huczynska, S., Mitchell, J. D. and Roney-Dougal, C. M.), pp. 19–73. London Mathematical Society Lecture Note Series 365, Cambridge University Press, Cambridge, 2009.Google Scholar
Bailey, R. A. and Cameron, Peter J., Using graphs to find the best block designs. In Topics in Structural Graph Theory (eds. Beineke, L. W. and Wilson, R. J.), Encyclopedia of Mathematics and its Applications 147, pp. 282–317. Cambridge University Press, Cambridge, 2013.Google Scholar
Bailey, R. A., Cameron, Peter J., Soicher, L. H. and Williams, E. R., Substitutes for the non-existent square lattice designs for 36 varieties, Journal of Biological, Agricultural and Environmental Statistics, 25 (2020), 487–499.CrossRefGoogle Scholar
Bailey, R. A. and Sajjad, Alia, Optimal incomplete-block designs with low replication: A unified approach using graphs, Journal of Statistical Theory and Practice, 15:84 (2021).CrossRefGoogle Scholar
Beth, T., Jungnickel, D. and Lenz, H., Design Theory, 2nd edition, Cambridge University Press, Cambridge, 1999, 2011.Google Scholar
Cakiroglu, S. A., Optimal regular graph designs, Statistics and Computing 28 (2018), 103–112.CrossRefGoogle Scholar
Cameron, P. J., Combinatorics: Topics, Techniques, Algorithms. Cambridge University Press, Cambridge, 1996.Google Scholar
Chêng, C.-S., Optimality of certain asymmetrical experimental designs, Annals of Statistics 6 (1978), 1239–1261.CrossRefGoogle Scholar
Chêng, C.-S., Maximizing the total number of spanning trees in a graph: two related problems in graph theory and optimum design theory, Journal of Combinatorial Theory Series B 31 (1981), 240–248.CrossRefGoogle Scholar
Cheng, C.-S. and Bailey, R. A., Optimality of some two-associate-class partially balanced incomplete-block designs, Annals of Statistics 19 (1991), 1667–1671.CrossRefGoogle Scholar
Christensen, R., Plane Answers to Complex Questions: The Theory of Linear Models. Springer-Verlag, New York, 1987.CrossRefGoogle Scholar
Clarke, B. R., Linear Models: The Theory and Application of Analysis of Variance. John Wiley & Sons, Hoboken, 2008.CrossRefGoogle Scholar
Hanani, H., The existence and construction of balanced incomplete block designs, Annals of Mathematical Statistics 32 (1961), 361–386.CrossRefGoogle Scholar
Hoffman, A. J. and Singleton, R. R., On Moore graphs with diameters 2 and 3, IBM J. Research Development 4 (1960), 497–504.CrossRefGoogle Scholar
Holton, Derek and Sheehan, John, The Petersen Graph, Australian Mathematical Society Lecture Series 7, Cambridge University Press, Cambridge, 1993.CrossRefGoogle Scholar
Kagan, M. and Mata, B., A physics perspective on the resistance distance for graphs, Mathematics in Computer Science 13 (2019), 105–115.CrossRefGoogle Scholar
Kiefer, J., Construction and optimality of generalized Youden designs. In A Survey of Statistical Design and Linear Models (ed. Srivastava, J. N.), pp. 333–353. North-Holland, Amsterdam (1975).Google Scholar
Krivelevich, M. and Sudakov, B., Sparse pseudo-random graphs are Hamiltonian, Journal of Graph Theory 42 (2003), 17–33.CrossRefGoogle Scholar
Kshirsagar, A. M., A note on incomplete block designs, Annals of Mathematical Statistics 29 (1958), 907–910.CrossRefGoogle Scholar
Mednykh, A. D. and Mednykh, I. A., On the structure of the Jacobian group of cir-culant graphs. (Russian) Dokl. Akad. Nauk 469 (2016), no. 5, 539–543; translation in Dokl. Math. 94 (2016), no. 1, 445–449.Google Scholar
Mohar, B., Some applications of Laplace eigenvalues of graphs. In Graph Symmetry: Algebraic Methods and Applications (eds. Hahn, G. and Sabidussi, G.), pp. 225–275. Springer, Dordrecht, 1997.Google Scholar
Morgan, J. P. and Srivastav, S. K., The completely symmetric designs with block-size three, Journal of Statistical Planning and Inference 106 (2002), 21–30.CrossRefGoogle Scholar
Saville, D. J. and Wood, G. R., Statistical Methods: A Geometric Primer. Springer-Verlag, New York, 1996.CrossRefGoogle Scholar
Shah, K. R. and Sinha, B. K., Theory of Optimal Designs, Lecture Notes in Statistics 54, Springer-Verlag, New York, 1989.CrossRefGoogle Scholar