no. 11 · Monday 9 November 2026
An Expander Mixing Lemma for Directed Graphs via Transition Matrices
Abstract
We establish an Expander Mixing Lemma for directed graphs in terms of the eigenvalues of a transition matrix, extending the classical spectral inequality to the non-symmetric setting. This formulation works with the complex spectrum of the transition matrix and incorporates the conditioning of its eigenbasis through a condition number. For connected, non-bipartite, undirected regular graphs, the result reduces to the classical Expander Mixing Lemma. More generally, the theorem provides a framework for studying structural properties of directed graphs through the spectra of non-normal matrices.
- comments
- 7 pages. Replacement: An earlier version of this paper contained an application to the toughness of directed graphs; that application has been withdrawn because its proof contained errors
- fields
- Combinatorics