- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Adapted metrics and random walks on graphs
Open Collections
UBC Theses and Dissertations
UBC Theses and Dissertations
Adapted metrics and random walks on graphs Folz, Matthew Bryan
Abstract
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.
Item Metadata
Title |
Adapted metrics and random walks on graphs
|
Creator | |
Publisher |
University of British Columbia
|
Date Issued |
2013
|
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.
|
Genre | |
Type | |
Language |
eng
|
Date Available |
2013-08-29
|
Provider |
Vancouver : University of British Columbia Library
|
Rights |
Attribution-NonCommercial-NoDerivatives 4.0 International
|
DOI |
10.14288/1.0074191
|
URI | |
Degree | |
Program | |
Affiliation | |
Degree Grantor |
University of British Columbia
|
Graduation Date |
2013-11
|
Campus | |
Scholarly Level |
Graduate
|
Rights URI | |
Aggregated Source Repository |
DSpace
|
Item Media
Item Citations and Data
Rights
Attribution-NonCommercial-NoDerivatives 4.0 International