Spectral and Algebraic Graph Theory (Draft)

Preface
Contents
Notation
I Introduction and Background
Introduction
Graphs
Matrices for Graphs
A spreadsheet
An operator
A quadratic form
Spectral Theory
Some examples
Paths
Highlights
Spectral Graph Drawing
Graph Isomorphism
Platonic Solids
The Fiedler Value
Bounding Eigenvalues
Planar Graphs
Random Walks on Graphs
Expanders
Approximations of Graphs
Solving equations in and computing eigenvalues of Laplacians
Exercises
Eigenvalues and Optimization: The Courant-Fischer Theorem
The First Proof
Proof of the Spectral Theorem
Notes
Exercise
The Laplacian and Graph Drawing
The Laplacian Matrix
Drawing with Laplacian Eigenvalues
Adjacency matrices, Eigenvalue Interlacing, and the Perron-Frobenius Theorem
The Adjacency Matrix
The Largest Eigenvalue, mu1
Eigenvalue Interlacing
Wilf's Theorem
Perron-Frobenius Theory for symmetric matrices
Comparing Graphs
Overview
The Loewner order
Approximations of Graphs
The Path Inequality
Bounding lambda2 of a Path Graph
The Complete Binary Tree
The weighted path
Exercises
II The Zoo of Graphs
Fundamental Graphs
The complete graph
The star graphs
Products of graphs
The Hypercube
Bounds on lambda2 by test vectors
The Ring Graph
The Path Graph
Cayley Graphs
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
Eigenvalues of Random Graphs
Transformation and Moments
The extreme eigenvalues
Expectation of the trace of a power
The number of walks
Notes
Exercise
Strongly Regular Graphs
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
III Physical Metaphors
Random Walks on Graphs
Random Walks
Spectra of Walk Matrices
The stable distribution
The Rate of Convergence
Relation to the Normalized Laplacian
Examples
The Path
The Complete Binary Tree
The Dumbbell
The Bolas Graph
Diffusion
Final Notes
Walks, Springs, and Resistor Networks
Overview
Harmonic Functions
Random Walks on Graphs
Spring Networks
Laplacian linear equations
Energy
Resistor Networks
Solving for currents
Exercise
Effective Resistance and Schur Complements
Electrical Flows and Effective Resistance
Effective Resistance through Energy Minimization
Monotonicity
Examples: Series and Parallel
Equivalent Networks, Elimination, and Schur Complements
In matrix form by energy
Eliminating Many Vertices
An interpretation of Gaussian elimination
Effective Resistance is a Distance
Random Spanning Trees
Introduction
Determinants
Characteristic Polynomials
The Matrix Tree Theorem
Leverage Scores and Marginal Probabilities
Approximating Effective Resistances
Representing Effective Resistances
Computing Effective Resistances
Properties of Gaussian random variables
Proof of Johnson-Lindenstrauss
Tutte's Theorem: How to draw a graph
3-Connected, Planar Graphs
Strictly Convex Polygons
Possible Degeneracies
All faces are convex
Notes
The Lovàsz - Simonovits Approach to Random Walks
Introduction
Definitions and Elementary Observations
Warm up
The proof
Andersen's proof of Cheeger's inequality
Monotonicity and its Failures
Disclaimer
Overview
Effective Spring Constants
Monotonicity
Effective Resistance
Examples
Breakdown of Monotonicity
Traffic Networks
Braes's Paradox
The Price of Anarchy
Nash optimum
Social optimum
Dynamic and Nonlinear Networks
Disclaimer
Overview
Non-Linear Networks
Energy
Uses in Semi-Supervised Learning
Dual Energy
Thermistor Networks
Low Temperatures
IV Spectra and Graph Structure
Independent Sets and Coloring
Overview
Graph Coloring and Independent Sets
Hoffman's Bound
Application to Paley graphs
Lower Bound on the chromatic number
Proofs for Hoffman's lower bound on chromatic number
Graph Partitioning
Isoperimetry and lambda2
Conductance
The Normalized Laplacian
Notes
Cheeger's Inequality
Cheeger's Inequality
Local Graph Clustering
The Algorithm
Good choices for a
Bounding the D-norm
Bounding the Generalized Rayleigh Quotient
Rounding
Notes
Spectral Partitioning in a Stochastic Block Model
The Perturbation Approach
Perturbation Theory for Eigenvectors
Partitioning
Proof of the Davis-Kahan Theorem
Further Reading
Nodal Domains
Overview
Sylverter's Law of Interia
Weighted Trees
More linear algebra
The Perron-Frobenius Theorem for Laplacians
Eigenvalue Interlacing
Fiedler's Nodal Domain Theorem
The Second Eigenvalue of Planar Graphs
Overview
Geometric Embeddings
The center of gravity
Further progress
Planar Graphs 2, the Colin de Verdière Number
Introduction
Colin de Verdière invariant
Polytopes and Planar Graphs
The Colin de Verdière Matrix
Minors of Planar Graphs
cdvG
V Expander Graphs
Properties of Expander Graphs
Overview
Expanders as Approximations of the Complete Graph
Quasi-Random Properties of Expanders
Vertex Expansion
How well can a graph approximate the complete graph?
Open Problems
A brief introduction to Coding Theory
Coding
Notation
Connection with Generalized Hypercubes
Hamming Codes
Terminology and Linear Codes
Random Linear Codes
Reed-Solomon Codes
Caution
Expander Codes
Bipartite Expander Graphs
Building Codes
Encoding
Minimum Distance
Decoding
Historical Notes
A simple construction of expander graphs
Overview
Squaring Graphs
The Relative Spectral Gap
Line Graphs
The Spectrum of the Line Graph
Approximations of Line Graphs
The whole construction
Better Constructions
PSRGs via Random Walks on Graphs
Overview
Why Study PSRGs?
Expander Graphs
Today's Application : repeating an experiment
The Random Walk Generator
Formalizing the problem
Matrix Norms
The norm of DXW
Conclusion
Notes
VI Algorithms
Sparsification by Random Sampling
Overview
Sparsification
Matrix Chernoff Bounds
The key transformation
The probabilities
The analysis
Open Problem
Linear Sized Sparsifiers
Overview
Turning edges into vectors
The main theorem
Rank-1 updates
Barrier Function Arguments
Barrier Function Updates
The inductive argument
Progress and Open Problems
Iterative solvers for linear equations
Why iterative methods?
First-Order Richardson Iteration
Expanders
The norm of the residual
A polynomial approximation of the inverse
Better Polynomials
Chebyshev Polynomials
Proof of Theorem 34.6.1
Laplacian Systems
Warning
The Conjugate Gradient and Diameter
The Matrix Norm
Application: Approximating Fiedler Vectors
Optimality in the A-norm
How Good is CG?
Laplacian Systems, again
Bounds on the Diameter
Preconditioning Laplacians
Approximate Solutions
Iterative Refinement
Iterative Methods in the Matrix Norm
Preconditioned Iterative Methods
Preconditioning by Trees
Improving the Bound on the Running Time
Further Improvements
Questions
Augmented Spanning Tree Preconditioners
Recursion
Heavy Trees
Saving a log
Fast Laplacian Solvers by Sparsification
Overview
Today's notion of approximation
The Idea
A symmetric expansion
D and A
Sketch of the construction
Making the construction efficient
Improvements
Testing Isomorphism of Graphs with Distinct Eigenvalues
Introduction
Graph Isomorphism
Using Eigenvalues and Eigenvectors
An easy case
All the Automorphisms
Equivalence Classes of Vertices
The first partition
Unbalanced vectors
The structure of the balanced classes
Algorithms
Testing Isomorphism of Strongly Regular Graphs
Introduction
Definitions
Paley Graphs and The Pentagon
Lattice Graphs
Latin Square Graphs
The Eigenvalues of Strongly Regular Graphs
Testing Isomorphism by Individualization and Refinement
Distinguishing Sets for Strongly Regular Graphs
Notes
VII Interlacing Families
Bipartite Ramanujan Graphs
Overview
2-Lifts
Random 2-Lifts
Laplacianized Polynomials
Interlacing Families of Polynomials
Common Interlacings
Real Rootedness
Conclusion
Overview
2dm-1
The Matching Polynomial
Properties of the Matching Polynomial
The Path Tree
Expected Characteristic Polynomials
Overview
Random sums of graphs
Interlacing
Sums of polynomials
Random Swaps
Quadrature for the Finite Free Convolution
Overview
The Finite Free Convolution
Quadrature
Quadrature by Invariance
Structure of the Orthogonal Group
The Formula
Question
Ramanujan Graphs of Every Size
Overview
The Approach
Interlacing Families of Polynomials
Root Bounds for Finite Free Convolutions
The Calculation
Some explanation of Theorem 44.4.1
Some thoughts
Matching Polynomials of Graphs
Overview
The Matching Polynomial
Properties of the Matching Polynomial
The Path Tree
Root bounds
Bipartite Ramanujan Graphs of Every Degree
Overview
2-Lifts
Random 2-Lifts
Bibliography
Index