TY - JOUR
T1 - Ultrametric subsets with large Hausdorff dimension
AU - Mendel, Manor
AU - Naor, Assaf
N1 - Funding Information:
M.M. was partially supported by ISF grants 221/07 and 93/11, BSF grants 2006009 and 2010021, and a gift from Cisco Research Center. A.N. was partially supported by NSF grant CCF-0832795, BSF grants 2006009 and 2010021, and the Packard Foundation. Part of this work was completed when M.M. was visiting Microsoft Research and University of Washington, and A.N. was visiting the Discrete Analysis program at the Isaac Newton Institute for Mathematical Sciences and the Quantitative Geometry program at the Mathematical Sciences Research Institute.
PY - 2013/4
Y1 - 2013/4
N2 - It is shown that for every ε∈(0,1), every compact metric space (X,d) has a compact subset S⊆X that embeds into an ultrametric space with distortion O(1/ε), and dimH(S),≥(1-ε)dimH(X) where dimH(·) denotes Hausdorff dimension. The above O(1/ε) distortion estimate is shown to be sharp via a construction based on sequences of expander graphs.
AB - It is shown that for every ε∈(0,1), every compact metric space (X,d) has a compact subset S⊆X that embeds into an ultrametric space with distortion O(1/ε), and dimH(S),≥(1-ε)dimH(X) where dimH(·) denotes Hausdorff dimension. The above O(1/ε) distortion estimate is shown to be sharp via a construction based on sequences of expander graphs.
UR - http://www.scopus.com/inward/record.url?scp=84874956329&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84874956329&partnerID=8YFLogxK
U2 - 10.1007/s00222-012-0402-7
DO - 10.1007/s00222-012-0402-7
M3 - Article
AN - SCOPUS:84874956329
VL - 192
SP - 1
EP - 54
JO - Inventiones Mathematicae
JF - Inventiones Mathematicae
SN - 0020-9910
IS - 1
ER -