TY - JOUR
T1 - Quasisymmetric embeddings, the observable diameter, and expansion properties of graphs
AU - Naor, Assaf
AU - Rabani, Yuval
AU - Sinclair, Alistair
N1 - Funding Information:
∗ Corresponding author. Fax: +1 425 936 7329. E-mail addresses: [email protected] (A. Naor), [email protected] (Y. Rabani), [email protected] (A. Sinclair). 1This work was done while the author was on sabbatical leave at Cornell University. Part of this work was done while the author was visiting Microsoft Research, Redmond. 2Supported in part by NSF ITR grant CCR-0121555. Part of this work was done while the author was on sabbatical leave at Microsoft Research, Redmond.
PY - 2005/10/15
Y1 - 2005/10/15
N2 - 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 (√log n) 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.
AB - 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 (√log n) 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.
KW - Edge expansion
KW - Observable diameter
KW - Quasisymmetric embeddings
KW - Vertex expansion
UR - http://www.scopus.com/inward/record.url?scp=25444434660&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=25444434660&partnerID=8YFLogxK
U2 - 10.1016/j.jfa.2005.04.003
DO - 10.1016/j.jfa.2005.04.003
M3 - Article
AN - SCOPUS:25444434660
SN - 0022-1236
VL - 227
SP - 273
EP - 303
JO - Journal of Functional Analysis
JF - Journal of Functional Analysis
IS - 2
ER -