Department of Mathematics,
University of California San Diego
****************************
Final Defense
Sinan Aksoy
UC San Diego
Random walks on directed graphs and orientations of graphs
Abstract:
We apply spectral theory to study random processes involving directed graphs. In the first half of this talk, 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 has ``many'' strong orientations. Furthermore, we provide constructions that show our conditions are essentially best possible. In the second half, 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. These invariants include the principal ratio of the stationary distribution and the first nontrivial Laplacian eigenvalue. Finally, we conclude by briefly exploring future related work.
Advisor: Fan Chung Graham
June 5, 2017
10:00 AM
AP&M 6402
****************************