Spectral Bounds for Directed Graphs Via Asymmetric Matrices: Applications to Toughness
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866909884643016704 |
|---|---|
| author | Carter, Rebecca |
| author_facet | Carter, Rebecca |
| contents | We establish an Expander Mixing Lemma for directed graphs in terms of the eigenvalues of an associated asymmetric transition probability matrix, extending the classical spectral inequality to the asymmetric setting. As an application, we derive a spectral bound on the toughness of directed graphs that generalizes Alon's bound for $k$-regular graphs, showing how structural properties of directed graphs can be captured through their asymmetric spectra. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_01738 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Spectral Bounds for Directed Graphs Via Asymmetric Matrices: Applications to Toughness Carter, Rebecca Combinatorics 05C20 (Primary) 05C42 (Secondary) We establish an Expander Mixing Lemma for directed graphs in terms of the eigenvalues of an associated asymmetric transition probability matrix, extending the classical spectral inequality to the asymmetric setting. As an application, we derive a spectral bound on the toughness of directed graphs that generalizes Alon's bound for $k$-regular graphs, showing how structural properties of directed graphs can be captured through their asymmetric spectra. |
| title | Spectral Bounds for Directed Graphs Via Asymmetric Matrices: Applications to Toughness |
| topic | Combinatorics 05C20 (Primary) 05C42 (Secondary) |
| url | https://arxiv.org/abs/2511.01738 |