Back to search

University of British Columbia

Adapted metrics and random walks on graphs

Abstract

dc:description

This thesis discusses various aspects of continuous-time simple random walks on measure weighted graphs, with a focus on behaviors related to large-scale geometric properties of the underlying graph. In contrast to previous work in this area, the majority of the results presented here are applicable to random walks with unbounded generators. A recurring theme in this research is the use of novel distance functions for graphs known as adapted metrics, which are demonstrated to be a powerful tool for studying random walks on graphs. Chapter 2 provides an overview of the relevant probabilistic and analytic theory, and provides multiple constructions of the heat kernel and a brief introduction to the theory of Dirichlet forms. Chapter 3 introduces adapted metrics, which play a central role in the following chapters, and which are especially useful in understanding random walks with unbounded generators. Chapter 4 discusses heat kernel estimates, and presents an overview of on-diagonal heat kernel estimates for graphs, as well as techniques for obtaining various off-diagonal estimates of the heat kernel. The off-diagonal estimates were proved by the author, and are notable for their use of adapted metrics. Chapter 5 introduces metric graphs, a continuous analogue of graphs which possess many desirable analytic properties, and analyzes the problem of constructing a Brownian motion on a metric graph which behaves similarly to a given continuous-time simple random walk. Chapter 6 analyzes recurrence and transience of graphs, and proves an original estimate relating adapted volume growth to recurrence of graphs. Chapter 7 discusses bounds for the bottom of the essential spectrum in terms of geometric inequalities such as volume growth estimates and isoperimetric inequalities. The main result of this chapter was proved by the author, and establishes sharp estimates for the bottom of the spectrum in terms of the adapted volume growth. Chapter 8 considers stochastic completeness of graphs and proves sharp criteria relating volume growth to stochastic completeness. The results of this chapter were proved by the author, using the machinery of metric graphs.

Degree

thesis:*
Name thesis:degree_name
Doctor of Philosophy - PhD
Level thesis:degree_level
doctoral
Discipline thesis:degree_discipline
Mathematics
Grantor dc:publisher
University of British Columbia
Year dc:date
2013

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Folz, Matthew Bryan

Rights

dc:rights
Statement dc:rights
  • Attribution-NonCommercial-NoDerivatives 4.0 International
Language dc:language
eng

Identifiers

dc:identifier.*
Handle dc:identifier
http://hdl.handle.net/2429/44947

Chain of custody

source
Harvested from
University of British Columbia
Base URL
circle.library.ubc.ca/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Folz, Matthew Bryan. Adapted metrics and random walks on graphs. doctoral thesis, University of British Columbia, 2013. http://hdl.handle.net/2429/44947