Transcription
Spectral and Algebraic Graph TheoryIncomplete Draft, dated December 4, 2019Current version available at el A. SpielmanYale UniversityCopyright c 2019 by Daniel A. Spielman. All rights reserved.
Chapter ListPrefacevContentsviNotationxxiiIIntroduction 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 Graphs39II46The Zoo of Graphs6 Fundamental Graphs477 Cayley Graphs558 Eigenvalues of Random Graphs639 Strongly Regular Graphs73i
CHAPTER LISTIIIPhysical Metaphorsii8210 Random Walks on Graphs8311 Walks, Springs, and Resistor Networks9312 Effective Resistance and Schur Complements10113 Random Spanning Trees11014 Approximating Effective Resistances11715 Tutte’s Theorem: How to draw a graph12216 The Lovàsz - Simonovits Approach to Random Walks13017 Monotonicity and its Failures13518 Dynamic and Nonlinear Networks143IV151Spectra and Graph Structure19 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ère Number199
CHAPTER LISTVExpander Graphsiii20627 Properties of Expander Graphs20728 A brief introduction to Coding Theory21629 Expander Codes22430 A simple construction of expander graphs23131 PSRGs via Random Walks on Graphs239VI245Algorithms32 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 Graphs305VIIInterlacing 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 Degree358Bibliography363Index375
PrefacePlease note that this is a rapidly evolving draft.This 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. After gaining intuition, I hope the reader willappreciate the material for its beauty.This 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 intuition.There 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 graph.This is obvious to those who understand it, but it can take a while for students to grasp. 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 theory.I 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,v
PREFACEvi“Spectral Graph Theory” by Fan Chung,“Algebraic Combinatorics” by Chris Godsil, and“Algebraic Graph Theory” by Chris Godsil and Gordon Royle.Other 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. 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 Wilmer.I include some example in these notes. All of these have been generated inside Jupyter notebooksusing the Julia language. Some of them require use of the package Laplacians.jl. A simple searchwill produce good instructions for installing Julia and packages for it. The notebooks used in thisbook may be found at http://cs-www.cs.yale.edu/homes/spielman/sagt.
n and Background11 Introduction21.1Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .21.2Matrices for Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .31.2.1A spreadsheet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .31.2.2An operator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .41.2.3A quadratic form . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .51.3Spectral Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .51.4Some examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .61.4.1Paths . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .6Highlights . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .91.5.1Spectral Graph Drawing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .91.5.2Graph Isomorphism . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131.5.3Platonic Solids . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141.5.4The Fiedler Value . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161.5.5Bounding Eigenvalues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171.5vii
CONTENTSviii1.5.6Planar Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171.5.7Random Walks on Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171.5.8Expanders . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171.5.9Approximations of Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181.5.10 Solving equations in and computing eigenvalues of Laplacians . . . . . . . . . 181.6Exercises. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182 Eigenvalues and Optimization: The Courant-Fischer Theorem212.1The First Proof . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222.2Proof of the Spectral Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242.3Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 262.4Exercise . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 263 The Laplacian and Graph Drawing273.1The Laplacian Matrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 273.2Drawing with Laplacian Eigenvalues . . . . . . . . . . . . . . . . . . . . . . . . . . . 294 Adjacency matrices, Eigenvalue Interlacing, and the Perron-Frobenius Theorem 324.1The Adjacency Matrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 324.2The Largest Eigenvalue, µ1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 334.3Eigenvalue Interlacing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 344.4Wilf’s Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 354.5Perron-Frobenius Theory for symmetric matrices . . . . . . . . . . . . . . . . . . . . 365 Comparing Graphs395.1Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 395.2The Loewner order . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 395.3Approximations of Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 415.4The Path Inequality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 415.4.15.5Bounding λ2 of a Path Graph . . . . . . . . . . . . . . . . . . . . . . . . . . . 42The Complete Binary Tree. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
CONTENTSIIix5.6The weighted path . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 445.7Exercises. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45The Zoo of Graphs6 Fundamental Graphs46476.1The complete graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 476.2The star graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 486.3Products of graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 496.3.1The Hypercube . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 506.4Bounds on λ2 by test vectors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 516.5The Ring Graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 526.6The Path Graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 537 Cayley Graphs557.1Cayley Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 557.2Paley Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 567.3Eigenvalues of the Paley Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 577.4Generalizing Hypercubes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 587.5A random set of generators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 597.6Conclusion7.7Non-Abelian Groups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 617.8Eigenvectors of Cayley Graphs of Abelian Groups . . . . . . . . . . . . . . . . . . . . 62. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 618 Eigenvalues of Random Graphs638.1Transformation and Moments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 648.2The extreme eigenvalues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 658.3Expectation of the trace of a power . . . . . . . . . . . . . . . . . . . . . . . . . . . . 668.4The number of walks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 688.5Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 718.6Exercise . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
CONTENTS9 Strongly Regular Graphsx739.1Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 739.2Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 739.3The Pentagon . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 749.4Lattice Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 749.5Latin Square Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 749.6The Eigenvalues of Strongly Regular Graphs9.7Regular graphs with three eigenvalues . . . . . . . . . . . . . . . . . . . . . . . . . . 769.8Integrality of the eigenvalues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 769.9The Eigenspaces of Strongly Regular Graphs . . . . . . . . . . . . . . . . . . . . . . 77. . . . . . . . . . . . . . . . . . . . . . 759.10 Triangular Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 789.11 Paley Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 799.12 Two-distance point sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80IIIPhysical Metaphors10 Random Walks on Graphs828310.1 Random Walks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8310.2 Spectra of Walk Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8410.3 The stable distribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8510.4 The Rate of Convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8610.5 Relation to the Normalized Laplacian . . . . . . . . . . . . . . . . . . . . . . . . . . 8710.6 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8910.6.1 The Path . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8910.6.2 The Complete Binary Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8910.6.3 The Dumbbell . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9010.6.4 The Bolas Graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9110.7 Diffusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9110.8 Final Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
CONTENTS11 Walks, Springs, and Resistor Networksxi9311.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9311.2 Harmonic Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9311.3 Random Walks on Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9411.4 Spring Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9411.5 Laplacian linear equations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9511.6 Energy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9711.7 Resistor Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9711.8 Solving for currents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9911.9 Exercise . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10012 Effective Resistance and Schur Complements10112.1 Electrical Flows and Effective Resistance . . . . . . . . . . . . . . . . . . . . . . . . . 10112.2 Effective Resistance through Energy Minimization . . . . . . . . . . . . . . . . . . . 10212.3 Monotonicity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10312.4 Examples: Series and Parallel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10412.5 Equivalent Networks, Elimination, and Schur Complements . . . . . . . . . . . . . . 10512.5.1 In matrix form by energy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10612.6 Eliminating Many Vertices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10712.7 An interpretation of Gaussian elimination . . . . . . . . . . . . . . . . . . . . . . . . 10812.8 Effective Resistance is a Distance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10813 Random Spanning Trees11013.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11013.2 Determinants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11013.3 Characteristic Polynomials . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11113.4 The Matrix Tree Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11213.5 Leverage Scores and Marginal Probabilities . . . . . . . . . . . . . . . . . . . . . . . 11414 Approximating Effective Resistances11714.1 Representing Effective Resistances . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
CONTENTSxii14.2 Computing Effective Resistances . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11814.3 Properties of Gaussian random variables . . . . . . . . . . . . . . . . . . . . . . . . . 11914.4 Proof of Johnson-Lindenstrauss . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12015 Tutte’s Theorem: How to draw a graph12215.1 3-Connected, Planar Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12215.2 Strictly Convex Polygons . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12515.3 Possible Degeneracies. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12615.4 All faces are convex . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12815.5 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12916 The Lovàsz - Simonovits Approach to Random Walks13016.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13016.2 Definitions and Elementary Observations. . . . . . . . . . . . . . . . . . . . . . . . 13116.3 Warm up . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13116.4 The proof . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13216.5 Andersen’s proof of Cheeger’s inequality . . . . . . . . . . . . . . . . . . . . . . . . . 13417 Monotonicity and its Failures13517.1 Disclaimer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13517.2 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13517.3 Effective Spring Constants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13517.4 Monotonicity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13617.5 Effective Resistance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13617.6 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13817.7 Breakdown of Monotonicity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13817.8 Traffic Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13917.9 Braes’s Paradox . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14017.10The Price of Anarchy. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14017.11Nash optimum . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14117.12Social optimum . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
CONTENTS18 Dynamic and Nonlinear Networksxiii14318.1 Disclaimer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14318.2 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14318.3 Non-Linear Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14318.4 Energy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14418.5 Uses in Semi-Supervised Learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14518.6 Dual Energy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14618.7 Thermistor Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14718.8 Low Temperatures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149IVSpectra and Graph Structure19 Independent Sets and Coloring15115219.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15219.2 Graph Coloring and Independent Sets . . . . . . . . . . . . . . . . . . . . . . . . . . 15219.3 Hoffman’s Bound . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15319.4 Application to Paley graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15419.5 Lower Bound on the chromatic number . . . . . . . . . . . . . . . . . . . . . . . . . 15519.6 Proofs for Hoffman’s lower bound on chromatic number . . . . . . . . . . . . . . . . 15620 Graph Partitioning15920.1 Isoperimetry and λ2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15920.2 Conductance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16120.3 The Normalized Laplacian . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16120.4 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16321 Cheeger’s Inequality16421.1 Cheeger’s Inequality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16422 Local Graph Clustering16922.1 The Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169
CONTENTSxiv22.2 Good choices for a . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17022.3 Bounding the D-norm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17222.4 Bounding the Generalized Rayleigh Quotient . . . . . . . . . . . . . . . . . . . . . . 17322.5 Rounding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17522.6 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17623 Spectral Partitioning in a Stochastic Block Model17723.1 The Perturbation Approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17823.2 Perturbation Theory for Eigenvectors. . . . . . . . . . . . . . . . . . . . . . . . . . 18023.3 Partitioning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18023.4 Proof of the Davis-Kahan Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18123.5 Further Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18324 Nodal Domains18424.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18424.2 Sylverter’s Law of Interia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18624.3 Weighted Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18724.4 More linear algebra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18924.4.1 The Perron-Frobenius Theorem for Laplacians . . . . . . . . . . . . . . . . . 18924.4.2 Eigenvalue Interlacing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18924.5 Fiedler’s Nodal Domain Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19025 The Second Eigenvalue of Planar Graphs19225.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19225.2 Geometric Embeddings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19325.3 The center of gravity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19625.4 Further progress . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19826 Planar Graphs 2, the Colin de Verdière Number19926.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19926.2 Colin de Verdière invariant . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 199
CONTENTSxv26.3 Polytopes and Planar Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20026.4 The Colin de Verdière Matrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20126.5 Minors of Planar Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20226.6 cdv(G) 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202VExpander Graphs27 Properties of Expander Graphs20620727.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20727.2 Expanders as Approximations of the Complete Graph . . . . . . . . . . . . . . . . . 20727.3 Quasi-Random Properties of Expanders . . . . . . . . . . . . . . . . . . . . . . . . . 20927.4 Vertex Expansion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21027.5 How well can a graph approximate the complete graph? . . . . . . . . . . . . . . . . 21127.6 Open Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21528 A brief introduction to Coding Theory21628.1 Coding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21628.2 Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21728.3 Connection with Generalized Hypercubes . . . . . . . . . . . . . . . . . . . . . . . . 21728.4 Hamming Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21728.5 Terminology and Linear Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21928.6 Random Linear Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22028.7 Reed-Solomon Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22228.8 Caution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22329 Expander Codes22429.1 Bipartite Expander Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22429.2 Building Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22629.3 Encoding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22629.4 Minimum Distance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22729.5 Decoding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 228
CONTENTSxvi29.6 Historical Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22930 A simple construction of expander graphs23130.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23130.2 Squaring Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23230.3 The Relative Spectral Gap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23330.4 Line Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23330.5 The Spectrum of the Line Graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23430.6 Approximations of Line Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23630.7 The whole construction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23730.8 Better Constructions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23831 PSRGs via Random Walks on Graphs23931.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23931.2 Why Study PSRGs? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23931.3 Expander Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24031.4 Today’s Application : repeating an experiment . . . . . . . . . . . . . . . . . . . . . 24031.5 The Random Walk Generator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24131.6 Formalizing the problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24131.7 Matrix Norms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24231.8 The norm of D X W . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24331.9 Conclusion. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24431.10Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 244VIAlgorithms32 Sparsification by Random Sampling24524632.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24632.2 Sparsification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24632.3 Matrix Chernoff Bounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24732.4 The key transformation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 248
CONTENTSxvii32.5 The probabilities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24832.6 The analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25032.7 Open Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25133 Linear Sized Sparsifiers25233.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25233.2 Turning edges into vectors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25233.3 The main theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25333.4 Rank-1 updates . . . . . . . . . . . . . . . . .
This book is mostly based on lecture notes from the \Spectral Graph Theory" course that I have taught at Yale, with notes from \Graphs and Networks" and \Spectral Graph Theory and its Applications" mixed in. I love the material in these courses, and nd that I can never teach
