Singular Values Versus Expansion in Directed and Undirected Graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916914699173888 |
|---|---|
| author | Ruotolo, Jake Vadhan, Salil |
| author_facet | Ruotolo, Jake Vadhan, Salil |
| contents | We relate the nontrivial singular values $σ_2,\ldots,σ_n$ of the normalized adjacency matrix of an Eulerian directed graph to combinatorial measures of graph expansion: \\ 1. We introduce a new directed analogue of conductance $ϕ_{dir}$, and prove a Cheeger-like inequality showing that $ϕ_{dir}$ is bounded away from 0 iff $σ_2$ is bounded away from 1. In undirected graphs, this can be viewed as a unification of the standard Cheeger Inequality and Trevisan's Cheeger Inequality for the smallest eigenvalue.\\ 2. We prove a singular-value analogue of the Higher-Order Cheeger Inequalities, giving a combinatorial characterization of when $σ_k$ is bounded away from 1. \\ 3. We tighten the relationship between $σ_2$ and vertex expansion, proving that if a $d$-regular graph $G$ with the property that all sets $S$ of size at most $n/2$ have at least $(1+δ)\cdot |S|$ out-neighbors, then $1-σ_2=Ω(δ^2/d)$. This bound is tight and saves a factor of $d$ over the previously known relationship. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_17539 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Singular Values Versus Expansion in Directed and Undirected Graphs Ruotolo, Jake Vadhan, Salil Combinatorics Discrete Mathematics 05C50 G.2.2 We relate the nontrivial singular values $σ_2,\ldots,σ_n$ of the normalized adjacency matrix of an Eulerian directed graph to combinatorial measures of graph expansion: \\ 1. We introduce a new directed analogue of conductance $ϕ_{dir}$, and prove a Cheeger-like inequality showing that $ϕ_{dir}$ is bounded away from 0 iff $σ_2$ is bounded away from 1. In undirected graphs, this can be viewed as a unification of the standard Cheeger Inequality and Trevisan's Cheeger Inequality for the smallest eigenvalue.\\ 2. We prove a singular-value analogue of the Higher-Order Cheeger Inequalities, giving a combinatorial characterization of when $σ_k$ is bounded away from 1. \\ 3. We tighten the relationship between $σ_2$ and vertex expansion, proving that if a $d$-regular graph $G$ with the property that all sets $S$ of size at most $n/2$ have at least $(1+δ)\cdot |S|$ out-neighbors, then $1-σ_2=Ω(δ^2/d)$. This bound is tight and saves a factor of $d$ over the previously known relationship. |
| title | Singular Values Versus Expansion in Directed and Undirected Graphs |
| topic | Combinatorics Discrete Mathematics 05C50 G.2.2 |
| url | https://arxiv.org/abs/2508.17539 |