Spectral Graph Theory

Title......Page 1
Contents......Page 3
Preface......Page 7
1.1. Introduction......Page 8
1.2. The Laplacian and eigenvalues......Page 9
1.3. Basic facts about the spectrum of a graph......Page 13
1.4. Eigenvalues of weighted graphs......Page 19
1.5. Eigenvalues and random walks......Page 21
2.1. History......Page 30
2.2. The Cheeger constant of a graph......Page 31
2.3. The edge expansion of a graph......Page 32
2.4. The vertex expansion of a graph......Page 36
2.5. A characterization of the Cheeger constant......Page 39
2.6. Isoperimetric inequalities for cartesian products......Page 42
3.1. The diameter of a graph......Page 48
3.2. Eigenvalues and distances between two subsets......Page 50
3.3. Eigenvalues and distances among many subsets......Page 53
3.4. Eigenvalue upper bounds for manifolds......Page 55
4.1. Paths and sets of paths......Page 62
4.2. Flows and Cheeger constants......Page 63
4.3. Eigenvalues and routes with small congestion......Page 65
4.4. Routing in graphs......Page 67
4.5. Comparison theorems......Page 71
5.1. Quasi-randomness......Page 76
5.2. The discrepancy property......Page 78
5.3. The deviation of a graph......Page 84
5.4. Quasi-random graphs......Page 88
6.1. Probabilistic methods versus explicit constructions......Page 94
6.2. The expanders......Page 95
6.3. Examples of explicit constructions......Page 100
6.4. Applications of expanders in communication networks......Page 105
6.5. Constructions of graphs with small diameter and girth......Page 108
6.6. Weighted Laplacians and the Lovasz {) function......Page 110
7.1. Symmetrical graphs......Page 116
7.2. Cheeger constants of symmetrical graphs......Page 117
7.3. Eigenvalues of symmetrical graphs......Page 119
7.4. Distance transitive graphs......Page 121
7.5. Eigenvalues and group representation theory......Page 124
7.6. The vibrational spectrum of a graph......Page 126
8.1. Neumann eigenvalues and Dirichlet eigenvalues......Page 130
8.2. The Neumann eigenvalues of a subgraph......Page 131
8.3. Neumann eigenvalues and random walks......Page 133
8.4. Dirichlet eigenvalues......Page 135
8.5. A matrix-tree theorem and Dirichlet eigenvalues......Page 136
8.6. Determinants and invariant field theory......Page 138
9.1. Eigenfunctions......Page 142
9.2. Convex subgraphs of homogeneous graphs......Page 143
9.3. A Harnack inequality for homogeneous graphs......Page 145
9.4. Harnack inequalities for Dirichlet eigenvalues......Page 147
9.5. Harnack inequalities for Neumann eigenvalues......Page 149
9.6. Eigenvalues and diameters......Page 151
10.1. The heat kernel of a graph and its induced subgraphs......Page 152
10.2. Basic facts on heat kernels......Page 153
10.3. An eigenvalue inequality......Page 155
10.4. Heat kernel lower bounds......Page 157
10.5. Matrices with given row and column sums......Page 163
10.6. Random walks and the heat kernel......Page 168
11.1. The isoperimetric dimension of a graph......Page 170
11.2. An isoperimetric inequality......Page 172
11.3. Sobolev inequalities......Page 175
11.4. Eigenvalue bounds......Page 177
11.5. Generalizations to weighted graphs and subgraphs......Page 182
12.1. Several approaches for bounding convergence......Page 184
12.2. Logarithmic Sobolev inequalities......Page 187
12.3. A comparison theorem for the log-Sobolev constant......Page 192
12.4. Logarithmic Harnack inequalities......Page 194
12.5. The isoperimetric dimension and the Sobolev inequality......Page 198
Bibliography......Page 202
Index......Page 211