**CBMS Regional Conference Series in Mathematics**

Volume: 92;
1997;
212 pp;
Softcover

MSC: Primary 05;

Print ISBN: 978-0-8218-0315-8

Product Code: CBMS/92

List Price: $37.00

Individual Price: $29.60

**Electronic ISBN: 978-1-4704-2452-7
Product Code: CBMS/92.E**

List Price: $34.00

Individual Price: $27.20

#### You may also like

# Spectral Graph Theory

Share this page
*Fan R. K. Chung*

A co-publication of the AMS and CBMS

Beautifully written and elegantly presented, this book is based on 10 lectures given at the CBMS workshop on spectral graph theory in June 1994 at Fresno State University. Chung's well-written exposition can be likened to a conversation with a good teacher—one who not only gives you the facts, but tells you what is really going on, why it is worth doing, and how it is related to familiar ideas in other areas. The monograph is accessible to the nonexpert who is interested in reading about this evolving area of mathematics.

#### Readership

Graduate students and research mathematicians interested in graph theory and its relations to combinatorics, geometry, communication theory, computer science, algebra, and other areas of pure and applied mathematics.

#### Reviews & Endorsements

The book presents a very complete picture of how various properties of a graph—from Cheeger constants and diameters to more recent developments such as log-Sobolev constants and Harnack inequalities—are related to the spectrum.

Even though the point of view of the book is quite geometric, the methods and exposition are purely graph-theoretic. As a result, the book is quite accessible to a reader who does not have any background in geometry.

As the author writes, ‘the underlying mathematics of spectral graph theory through all its connections to the pure and applied, the continuous and discrete, can be viewed as a single unified subject.’

Anyone who finds this sentence appealing is encouraged to give this book a try. He or she will not be disappointed.

-- Mathematical Reviews

Incorporates a great deal of recent work, much of it due to the author herself … clear, without being pedantic, and challenging, without being obscure.

-- Bulletin of the London Mathematical Society

#### Table of Contents

# Table of Contents

## Spectral Graph Theory

- Cover Cover11 free
- Title v6 free
- Copyright vi7 free
- Contents vii8 free
- Preface xi12 free
- Chapter 1. Eigenvalues and the Laplacian of a graph 114 free
- Chapter 2. Isoperimetric problems 2336
- Chapter 3. Diameters and eigenvalues 4356
- Chapter 4. Paths, flows, and routing 5972
- Chapter 5. Eigenvalues and quasi-randomness 7386
- Chapter 6. Expanders and explicit constructions 91104
- 6.1. Probabilistic methods versus explicit constructions 91104
- 6.2. The expanders 92105
- 6.3. Examples of explicit constructions 97110
- 6.4. Applications of expanders in communication networks 102115
- 6.5. Constructions of graphs with small diameter and girth 105118
- 6.6. Weighted Laplacians and the Lovász υ function 107120

- Chapter 7. Eigenvalues of symmetrical graphs 113126
- Chapter 8. Eigenvalues of subgraphs with boundary conditions 127140
- 8.1. Neumann eigenvalues and Dirichlet eigenvalues 127140
- 8.2. The Neumann eigenvalues of a subgraph 128141
- 8.3. Neumann eigenvalues and random walks 130143
- 8.4. Dirichlet eigenvalues 132145
- 8.5. A matrix-tree theorem and Dirichlet eigenvalues 133146
- 8.6. Determinants and invariant field theory 135148

- Chapter 9. Harnack inequalities 139152
- Chapter 10. Heat kernels 149162
- Chapter 11. Sobolev inequalities 167180
- Chapter 12. Advanced techniques for random walks on graphs 181194
- Bibliography 201214
- Index 210223
- Back Cover Back Cover1228