●Preface
Chapter 1.Eigenvalues and the Laplacian of a graph
1.1.Introduction
1.2.The Laplacian and eigenvalues
1.3.Basic facts about the spectrum of a graph
1.4.Eigenvalues of weighted graphs
1.5.Eigenvalues and random walks
Chapter 2.Isoperimetric problems
2.1.History
2.2.The Cheeger constant of a graph
2.3.The edge expansion of a graph
2.4.The vertex expansion of a graph
2.5.A characterization of the Cheeger constant
2.6.Isoperimetric inequalities for cartesian products
Chapter 3.Diameters and eigenvalues
3.1.The diameter of a graph
3.2.Eigenvalues and distances between two subsets
3.3.Eigenvalues and distances among many subsets
3.4.Eigenvalue upper bounds for manifolds
Chapter 4.Paths， flows， and routing
4.1.Paths and sets of paths
4.2.Flows and Cheeger constants
4.3.Eigenvalues and routes with small congestion
4.4.Routing in graphs
4.5.Comparison theorems
Chapter 5.Eigenvalues and quasi-randomness
5.1.Quasi-randomness
5.2.The discrepancy property
5.3.The deviation of a graph
5.4.Quasi-random graphs
Chapter 6.Expanders and explicit constructions
6.1.Probabilistic methods versus explicit constructions
6.2.The expanders
6.3.Examples of explicit constructions
6.4.Applications of expanders in communication networks
6.5.Constructions of graphs with small diameter and girth
6.6.Weighted Laplacians and the Lovasz v function
Chapter 7.Eigenvalues of symmetrical graphs
7.1.Symmetrical graphs
7.2.Cheeger constants of symmetrical graphs
7.3.Eigenvalues of symmetrical graphs
7.4.Distance transitive graphs
7.5.Eigenvalues and group representation theory
7.6.The vibrational spectrum of a graph
Chapter 8.Eigenvalues of subgraphs with boundary conditions
8.1.Neumann eigenvalues and Dirichlet eigenvalues
8.2.The Neumann eigenvatues of a subgraph
8.3.Neumann eigenvalues and random walks
8.4.Dirichlet eigenvalues
8.5.A matrix-tree theorem and Dirichlet eigenvalues
8.6.Determinants and invariant field theory
Chapter 9.Harnack inequalities
9.1.Eigenfunctions
9.2.Convex subgraphs of homogeneous graphs
9.3.A Harnack inequality for homogeneous graphs
9.4.Harnack inequalities for Dirichlet eigenvalues
9.5.Harnack inequalities for Neumann eigenvalues
9.6.Eigenvalues and diameters
Chapter 10.Heat kernels
10.1.The heat kernel of a graph and its induced subgraphs
10.2.Basic facts on heat kernels
10.3.An eigenv e inequality
10.4.Heat kernel lower bounds
10.5.Matrices with given row and column sums
10.6.Random walks and the heat kernel
Chapter 11.Sobolev inequalities
11.1.The isoperimetric dimension of a graph
11.2.An isoperimetric inequality
11.3.Sobolev inequalities
11.4.Eigenvalue bounds
11.5.Generalizations to weighted graphs and subgraphs
Chapter 12.Advanced techniques for random walks on graphs
12.1.Several approaches for bounding convergence
12.2.Logarithmic Sobolev inequalities
12.3.A comparison theorem for the log-Sobolev constant
12.4.Logarithmic Harnack inequalities
12.5.The isoperimetric dimension and the Sobolev inequality
Bibliography
Index
