Random Walks on Directed Graphs and Orientations of Graphs PDF Download

Author: Sinan Güven Aksoy
Publisher:
ISBN:
Category :
Languages : en
Pages : 109

Get Book Here

Book Description
We apply spectral theory to study random processes involving directed graphs. In the first half of this thesis, we examine random walks on directed graphs, which is rooted in the study of non-reversible Markov chains. We prove bounds on key spectral invariants which play a role in bounding the rate of convergence of the walk and capture isoperimetric properties of the directed graph. We first focus on the principal ratio, which is the ratio of maximum to minimum values of vertices in the stationary distribution. Improving upon previous bounds, we give a sharp upper bound for this ratio over all strongly connected graphs on $n$ vertices. We characterize all graphs achieving the upper bound and give explicit constructions for these extremal graphs. Additionally, we show that under certain conditions, the principal ratio is tightly bounded. We then turn our attention to the first nontrivial Laplacian eigenvalue of a strongly connected directed graph. We give a lower bound for this eigenvalue, extending an analogous result for undirected graphs to the directed case. Our results on the principal ratio imply this lower bound can be factorially small in the number of vertices, and we give a construction having this eigenvalue factorially small. In the second half, we apply spectral tools to study orientations of graphs. We focus on counting orientations yielding strongly connected directed graphs, called strong orientations. Namely, we show that under a mild spectral and minimum degree condition, a possibly irregular, sparse graph $G$ has "many" strong orientations. More precisely, given a graph $G$ on $n$ vertices, orient each edge in either direction with probability $1/2$ independently. We show that if $G$ satisfies a minimum degree condition of $(1+c_1)\log_2{n}$ and has Cheeger constant at least $c_2\frac{\log_2\log_2{n}}{\log_2{n}}$, then the resulting randomly oriented directed graph is strongly connected with high probability. This Cheeger constant bound can be replaced by an analogous spectral condition via the Cheeger inequality. Additionally, we provide an explicit construction to show our minimum degree condition is tight while the Cheeger constant bound is tight up to a $\log_2\log_2{n}$ factor. We conclude by exploring related future work.