Random Walks and Heat Kernels on Graphs
This introduction to random walks
on infinite graphs gives particular emphasis to graphs with polynomial volume growth. It offers an overview of analytic methods,
starting with the connection between random walks and electrical resistance, and then proceeding to study the use of isoperimetric
and Poincare inequalities. The book presents rough isometries and looks at the properties of a graph that are stable under
these transformations. Applications include the 'type problem': determining whether a graph is transient or recurrent. The
final chapters show how geometric properties of the graph can be used to establish heat kernel bounds, that is, bounds on
the transition probabilities of the random walk, and it is proved that Gaussian bounds hold for graphs that are roughly isometric
to Euclidean space. Aimed at graduate students in mathematics, the book is also useful for researchers as a reference for
results that are hard to find elsewhere.
Preface; 1. Introduction; 2. Random walks and electrical resistance; 3. Isoperimetric
inequalities and applications; 4. Discrete time heat kernel; 5. Continuous time random walks; 6. Heat kernel bounds; 7. Potential
theory and Harnack inequalities; Appendix A; References; Index.
Useful but hard-to-find results enrich this introduction
to the analytic study of random walks on infinite graphs.