ÃÀ¹úÊýѧ»á¾­µäӰӡϵÁÐÆ×ͼÂÛ(Ó°Ó¡°æ)

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 eigenvMue 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