Discrepancy inequalities for 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 skew-discrepancy   of directed graphs which measures the difference of flow among two subsets. We show that the skew-discrepancy is intimately related to ZZ, the skew-symmetric part of the normalized probability transition matrix. In particular, we prove that the skew-discrepancy is within a logarithmic factor of ‖Z‖‖Z‖. 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.