Graduate Seminar - 5/01, 12:00PM Duncan Hall 1064

Franklin Kenter

"Spectral Properties of Directed Graphs"

We establish several discrepancy and isoperimetric inequalities for directed graphs by considering the associated random walk. We show that various isoperimetric parameters, as measured by the stationary distribution of the random walks, including the Cheeger constant and discrepancy are related to the singular values of the normalized probability matrix and the normalized Laplacian. Further, we consider the it skew-discrepancy of directed graphs which measures the difference of flow among two subsets. We show that the skew-discrepancy is intimately related to mathcalZ, the skew-symmetric part of the normalized probability transition matrix. In particular, we prove that the skew-discrepancy is within a logarithmic factor of mathcalZ. Finally, we apply our results to construct extremal families of directed graphs with large differences between the discrepancy of the underlying graph and the skew-discrepancy.

This is joint work with Fan Chung.