Laplacian eigenvalues and optimality

Research output: Chapter in Book/Report/Conference proceedingChapter (peer-reviewed)peer-review

Abstract

Eigenvalues of the Laplacian matrix of a graph have been widely used in studying connectivity and expansion properties of networks, and also in analysing 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, 5].
Original languageEnglish
Title of host publicationGroups and graphs, designs and dynamics
EditorsR. A. Bailey, Peter J. Cameron, Yaokun Wu
Place of PublicationCambridge
PublisherCambridge University Press
Chapter3
Pages176-265
Number of pages90
ISBN (Electronic)9781009465939
ISBN (Print)9781009465953
DOIs
Publication statusE-pub ahead of print - 11 May 2024

Publication series

NameLondon Mathematical Society lecture note series
Volume491
ISSN (Print)0076-0552

Keywords

  • Block design
  • Optimality
  • Resistance distance
  • Spanning trees

Fingerprint

Dive into the research topics of 'Laplacian eigenvalues and optimality'. Together they form a unique fingerprint.

Cite this