Skip to main content Accessibility help

We use cookies to distinguish you from other users and to provide you with a better experience on our websites. Close this message to accept cookies or find out how to manage your cookie settings.

Close cookie message
×
Hostname: page-component-745bb68f8f-5r2nc Total loading time: 0 Render date: 2025-01-12T21:40:50.841Z Has data issue: false hasContentIssue false

3 - Laplacian eigenvalues and optimality

Published online by Cambridge University Press:  11 May 2024

By
R. A. Bailey  and
Peter J. Cameron
Edited by
R. A. Bailey ,
Peter J. Cameron  and
Yaokun Wu
R. A. Bailey
Affiliation:
University of St Andrews, Scotland
Peter J. Cameron
Affiliation:
University of St Andrews, Scotland
Yaokun Wu
Affiliation:
Shanghai Jiao Tong University, China
Get access

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].

Keywords

block designoptimalityresistance distancespanning trees
Type
Chapter
Information
Groups and Graphs, Designs and Dynamics , pp. 176 - 265
Publisher: Cambridge University Press
Print publication year: 2024

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

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
Bollobás, B., Modern Graph Theory. Springer, New York, 1998.CrossRefGoogle Scholar
Bose memorial session, Sankhyā, Series B 54 (1992), i–viii.Google Scholar
Buekenhout, F. and Cohen, A. M., Diagram Geometry. Springer, Berlin, 2013.CrossRefGoogle 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

Save book to Kindle

To save this book to your Kindle, first ensure [email protected] is added to your Approved Personal Document E-mail List under your Personal Document Settings on the Manage Your Content and Devices page of your Amazon account. Then enter the ‘name’ part of your Kindle email address below. Find out more about saving to your Kindle.

Note you can select to save to either the @free.kindle.com or @kindle.com variations. ‘@free.kindle.com’ emails are free but can only be saved to your device when it is connected to wi-fi. ‘@kindle.com’ emails can be delivered even when you are not connected to wi-fi, but note that service fees apply.

Find out more about the Kindle Personal Document Service.

Available formats
×

Save book to Dropbox

To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Dropbox.

Available formats
×

Save book to Google Drive

To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Google Drive.

Available formats
×