Trees and Markov convexity

James R. Lee; Assaf Naor; Yuval Peres

doi:10.1007/s00039-008-0689-0

Trees and Markov convexity

James R. Lee, Assaf Naor, Yuval Peres

Research output: Contribution to journal › Article › peer-review

36 Scopus citations

Abstract

We show that an infinite weighted tree admits a bi-Lipschitz embedding into Hilbert space if and only if it does not contain arbitrarily large complete binary trees with uniformly bounded distortion. We also introduce a new metric invariant called Markov convexity, and show how it can be used to compute the Euclidean distortion of any metric tree up to universal factors.

Original language	English (US)
Pages (from-to)	1609-1659
Number of pages	51
Journal	Geometric and Functional Analysis
Volume	18
Issue number	5
DOIs	https://doi.org/10.1007/s00039-008-0689-0
State	Published - Feb 2009
Externally published	Yes

All Science Journal Classification (ASJC) codes

Analysis
Geometry and Topology

Keywords

Metric trees
Uniform convexity
bi-Lipschitz embeddings

Access to Document

10.1007/s00039-008-0689-0

Cite this

@article{b0ddf4b338fb427083347f280b581051,

title = "Trees and Markov convexity",

abstract = "We show that an infinite weighted tree admits a bi-Lipschitz embedding into Hilbert space if and only if it does not contain arbitrarily large complete binary trees with uniformly bounded distortion. We also introduce a new metric invariant called Markov convexity, and show how it can be used to compute the Euclidean distortion of any metric tree up to universal factors.",

keywords = "Metric trees, Uniform convexity, bi-Lipschitz embeddings",

author = "Lee, \{James R.\} and Assaf Naor and Yuval Peres",

year = "2009",

month = feb,

doi = "10.1007/s00039-008-0689-0",

language = "English (US)",

volume = "18",

pages = "1609--1659",

journal = "Geometric and Functional Analysis",

issn = "1016-443X",

publisher = "Birkhauser Verlag Basel",

number = "5",

}

TY - JOUR

T1 - Trees and Markov convexity

AU - Lee, James R.

AU - Naor, Assaf

AU - Peres, Yuval

PY - 2009/2

Y1 - 2009/2

N2 - We show that an infinite weighted tree admits a bi-Lipschitz embedding into Hilbert space if and only if it does not contain arbitrarily large complete binary trees with uniformly bounded distortion. We also introduce a new metric invariant called Markov convexity, and show how it can be used to compute the Euclidean distortion of any metric tree up to universal factors.

AB - We show that an infinite weighted tree admits a bi-Lipschitz embedding into Hilbert space if and only if it does not contain arbitrarily large complete binary trees with uniformly bounded distortion. We also introduce a new metric invariant called Markov convexity, and show how it can be used to compute the Euclidean distortion of any metric tree up to universal factors.

KW - Metric trees

KW - Uniform convexity

KW - bi-Lipschitz embeddings

UR - https://www.scopus.com/pages/publications/78651268384

UR - https://www.scopus.com/inward/citedby.url?scp=78651268384&partnerID=8YFLogxK

U2 - 10.1007/s00039-008-0689-0

DO - 10.1007/s00039-008-0689-0

M3 - Article

AN - SCOPUS:78651268384

SN - 1016-443X

VL - 18

SP - 1609

EP - 1659

JO - Geometric and Functional Analysis

JF - Geometric and Functional Analysis

IS - 5

ER -

Trees and Markov convexity

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this