Printable PDF
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

****************************