Spectral and Algebraic Graph Theory

1 Spectral and Algebraic Graph TheoryIncomplete Draft, dated December 4, 2019 Current version available A. SpielmanYale UniversityCopyrightc 2019 by Daniel A. Spielman. All rights ListPrefacevContentsviNotationxxiiI Introduction and Background11 Introduction22 Eigenvalues and optimization : The Courant-Fischer Theorem213 The Laplacian and Graph Drawing274 Adjacency matrices, Eigenvalue Interlacing, and the Perron-Frobenius Theorem 325 Comparing Graphs39II The Zoo of Graphs466 Fundamental Graphs477 Cayley Graphs558 Eigenvalues of Random Graphs639 Strongly Regular Graphs73iCHAPTER LISTiiIII Physical Metaphors8210 Random Walks on Graphs8311 Walks, Springs, and Resistor Networks9312 Effective Resistance and Schur Complements10113 Random Spanning Trees11014 Approximating Effective Resistances11715 Tutte s Theorem.

2 How to draw a graph12216 The Lov`asz - Simonovits Approach to Random Walks13017 Monotonicity and its Failures13518 Dynamic and Nonlinear Networks143IV Spectra and Graph Structure15119 Independent Sets and Coloring15220 Graph Partitioning15921 Cheeger s Inequality16422 Local Graph Clustering16923 Spectral Partitioning in a Stochastic Block Model17724 Nodal Domains18425 The Second Eigenvalue of Planar Graphs19226 Planar Graphs 2, the Colin de Verdi`ere Number199 chapter LISTiiiV Expander Graphs20627 Properties of Expander Graphs20728 A brief introduction to Coding Theory21629 Expander Codes22430 A simple construction of expander graphs23131 PSRGs via Random Walks on Graphs239VI Algorithms24532 Sparsification by Random Sampling24633 Linear Sized Sparsifiers25234 Iterative solvers for linear equations26035 The Conjugate Gradient and Diameter26836 Preconditioning Laplacians27537 Augmented Spanning Tree Preconditioners28338 Fast Laplacian Solvers by Sparsification28839 Testing Isomorphism of Graphs with Distinct Eigenvalues29540 Testing Isomorphism of Strongly Regular Graphs305 VII

3 Interlacing Families31341 Bipartite Ramanujan Graphs31442 Expected Characteristic Polynomials329 chapter LISTiv43 Quadrature for the Finite Free Convolution33644 Ramanujan Graphs of Every Size34445 Matching Polynomials of Graphs35246 Bipartite Ramanujan Graphs of Every Degree358 Bibliography363 Index375 PrefacePlease note that this is a rapidly evolving book is about how combinatorial properties of graphs are related to Algebraic properties ofassociated matrices, as well as applications of those connections. One s initial excitement over thismaterial usually stems from its counter-intuitive nature. I hope to convey this initial amazement,but then make the connections seem intuitive.

4 After gaining intuition, I hope the reader willappreciate the material for its book is mostly based on lecture notes from the Spectral Graph Theory course that I havetaught at Yale, with notes from Graphs and Networks and Spectral Graph Theory and itsApplications mixed in. I love the material in these courses, and find that I can never teacheverything I want to cover within one semester. This is why I am have written this book. As thisbook is based on lecture notes, it does not contain the tightest or most recent results. Rather, mygoal is to introduce the main ideas and to provide are three tasks that one must accomplish in the beginning of a course on Spectral GraphTheory: One must convey how the coordinates of eigenvectors correspond to vertices in a is obvious to those who understand it, but it can take a while for students to grasp.

5 One must introduce necessary linear algebra and show some interesting interpretations ofgraph eigenvalues. One must derive the eigenvalues of some example graphs to ground the find that one has to do all these at once. For this reason my first few lectures jump betweendeveloping Theory and examining particular graphs. For this book I have decided to organize thematerial differently, mostly separating examinations of particular graphs from the development ofthe Theory . To help the reader reconstruct the flow of my courses, I give three orders that I haveused for the material:put orders hereThere are many terrific books on Spectral Graph Theory . The four that influenced me the mostare Algebraic Graph Theory by Norman Biggs,vPREFACEvi Spectral Graph Theory by Fan Chung, Algebraic Combinatorics by Chris Godsil, and Algebraic Graph Theory by Chris Godsil and Gordon books that I find very helpful and that contain related material include Modern Graph Theory by Bela Bollobas, Probability on Trees and Networks by Russell Llyons and Yuval Peres, Spectra of Graphs by Dragos Cvetkovic, Michael Doob, and Horst Sachs, and Eigenspaces of Graphs By Dragos Cvetkovic, Peter Rowlinson, and Slobodan Simic Non-negative Matrices and Markov Chains by Eugene Seneta Nonnegative Matrices and Applications by R.

6 B. Bapat and T. E. S. Raghavan Numerical Linear Algebra by Lloyd N. Trefethen and David Bau, III Applied Numerical Linear Algebra by James W. DemmelFor those needing an introduction to linear algebra, a perspective that is compatible with thisbook is contained in Gil Strang s Introduction to Linear Algebra. For more advanced topics inlinear algebra, I recommend Matrix Analysis by Roger Horn and Charles Johnson, as well astheir Topics in Matrix Analysis For treatments of physical systems related to graphs, the topicof Part III, I recommend Gil Strang s Introduction to Applied Mathematics , Sydney H. Gould s Variational Methods for Eigenvalue Problems , and Markov Chains and Mixing Times byLevin, Peres and include some example in these notes.

7 All of these have been generated inside Jupyter notebooksusing the Julia language. Some of them require use of the package A simple searchwill produce good instructions for installing Julia and packages for it. The notebooks used in thisbook may be found Introduction and Background11 Graphs .. Matrices for Graphs .. spreadsheet .. operator .. quadratic form .. Spectral Theory .. Some examples .. Highlights .. Graph Drawing .. Isomorphism .. Solids .. Fiedler Value .. Eigenvalues .. Graphs .. Walks on Graphs .. of Graphs .. Solving equations in and computing eigenvalues of Laplacians .. Exercises.

8 182 Eigenvalues and optimization : The Courant-Fischer The First Proof .. Proof of the Spectral Theorem .. Notes .. Exercise .. 263 The Laplacian and Graph The Laplacian Matrix .. Drawing with Laplacian Eigenvalues .. 294 Adjacency matrices, Eigenvalue Interlacing, and the Perron-Frobenius Theorem The Adjacency Matrix .. The Largest Eigenvalue, 1.. Eigenvalue Interlacing .. Wilf s Theorem .. Perron-Frobenius Theory for symmetric matrices .. 365 Comparing Overview .. The Loewner order .. Approximations of Graphs .. The Path Inequality .. 2of a Path Graph .

9 The Complete Binary Tree .. The weighted path .. Exercises .. 45II The Zoo of Graphs466 Fundamental The complete Graph .. The star graphs .. Products of graphs .. Hypercube .. Bounds on 2by test vectors .. The Ring Graph .. The Path Graph .. 537 Cayley Cayley Graphs .. Paley Graphs .. Eigenvalues of the Paley Graphs .. Generalizing Hypercubes .. A random set of generators .. Conclusion .. Non-Abelian Groups .. Eigenvectors of Cayley Graphs of Abelian Groups .. 628 Eigenvalues of Random Transformation and Moments.

10 The extreme eigenvalues .. Expectation of the trace of a power .. The number of walks .. Notes .. Exercise .. 71 CONTENTSx9 Strongly Regular Introduction .. Definitions .. The Pentagon .. Lattice Graphs .. Latin Square Graphs .. The Eigenvalues of Strongly Regular Graphs .. Regular graphs with three eigenvalues .. Integrality of the eigenvalues .. The Eigenspaces of Strongly Regular Graphs .. Triangular Graphs .. Paley Graphs .. Two-distance point sets .. 80 III Physical Metaphors8210 Random Walks on Random Walks .. Spectra of Walk Matrices.