Ultrametric subsets with large Hausdorff dimension

Manor Mendel; Assaf Naor

doi:10.1007/s00222-012-0402-7

Ultrametric subsets with large Hausdorff dimension

Manor Mendel, Assaf Naor

מדעי המחשב

نتاج البحث: نشر في مجلة › مقالة › مراجعة النظراء

ملخص

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 dim_H(S),≥(1-ε)dim_H(X) where dim_H(·) denotes Hausdorff dimension. The above O(1/ε) distortion estimate is shown to be sharp via a construction based on sequences of expander graphs.

اللغة الأصلية	الإنجليزيّة
الصفحات (من إلى)	1-54
عدد الصفحات	54
دورية	Inventiones Mathematicae
مستوى الصوت	192
رقم الإصدار	1
المعرِّفات الرقمية للأشياء	https://doi.org/10.1007/s00222-012-0402-7
حالة النشر	نُشِر - أبريل 2013

ملاحظة ببليوغرافية

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.

الوصول إلى المستند

10.1007/s00222-012-0402-7

الملفات والروابط الأخرى

Link to publication in Scopus

قم بذكر هذا

@article{2f13a3e6719341c5853bda98ecda1249,

title = "Ultrametric subsets with large Hausdorff dimension",

abstract = "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.",

author = "Manor Mendel and Assaf Naor",

note = "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.",

year = "2013",

month = apr,

doi = "10.1007/s00222-012-0402-7",

language = "אנגלית",

volume = "192",

pages = "1--54",

journal = "Inventiones Mathematicae",

issn = "0020-9910",

publisher = "Springer New York",

number = "1",

}

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

U2 - 10.1007/s00222-012-0402-7

DO - 10.1007/s00222-012-0402-7

M3 - ???researchoutput.researchoutputtypes.contributiontojournal.article???

AN - SCOPUS:84874956329

SN - 0020-9910

VL - 192

SP - 1

EP - 54

JO - Inventiones Mathematicae

JF - Inventiones Mathematicae

IS - 1

ER -

Ultrametric subsets with large Hausdorff dimension

ملخص

ملاحظة ببليوغرافية

الوصول إلى المستند

الملفات والروابط الأخرى

بصمة

قم بذكر هذا