Singular Values Versus Expansion in Directed and Undirected Graphs
Jake Ruotolo and Salil Vadhan
我们把欧勒联定向图的标准化邻接矩阵的非平凡的奇异值 σ_2,...,σ_n 关联到图扩展的组合度量: 1. 我们引入了一个新的定向电导率 φ_dir 的模拟,并证明了一个类似 Cheeger 的不等式,表明 φ_dir 被绑定到 0 iff σ_2 之外。 在无方向图中,这可被视为标准Cheeger Inequality和Trevisan的Cheeger Inequality的统一,以获得最小的特征值。 2. 我们证明了高阶 Cheeger 不平等的奇数值类似物,给出了 σ_k 脱离 1 时的组合表征。 3. 我们收紧了σ_2和顶点扩展之间的关系,证明如果一个d-regular图G与属性的所有设置S的大小在最多n/2有至少(1+δ)·|S|外邻,那么1-σ_2=Ω(δ^2/d)。 这种约束是紧密的,并且节省了先前已知的关系的一个因子。
We relate the nontrivial singular values σ_2,…,σ_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 prov...