Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
9495420 | Journal of Functional Analysis | 2005 | 31 Pages |
Abstract
It is shown that the edges of any n-point vertex expander can be replaced by new edges so that the resulting graph is an edge expander, and such that any two vertices that are joined by a new edge are at distance O(logn) in the original graph. This result is optimal, and is shown to have various geometric consequences. In particular, it is used to obtain an alternative perspective on the recent algorithm of Arora et al. [Proceedings of the 36th Annual ACM Symposium on the Theory of Computing, 2004, pp. 222-231.] for approximating the edge expansion of a graph, and to give a nearly optimal lower bound on the ratio between the observable diameter and the diameter of doubling metric measure spaces which are quasisymmetrically embeddable in Hilbert space.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Algebra and Number Theory
Authors
Assaf Naor, Yuval Rabani, Alistair Sinclair,