Scale-oblivious metric fragmentation and the nonlinear Dvoretzky theorem

Details Scale-oblivious metric fragmentation and the nonlinear Dvoretzky theorem Scale-oblivious metric fragmentation and the nonlinear Dvoretzky theorem

2010-03-21

arxiv.org/abs/1003.4013v1

Mathematics

Metric Geometry

11 pages, no figures, submitted, Israel J. Math.

Scientific paper

We introduce a randomized iterative fragmentation procedure for finite metric spaces, which is guaranteed to result in a polynomially large subset that is $D$-equivalent to an ultrametric, where $D\in (2,\infty)$ is a prescribed target distortion. Since this procedure works for $D$ arbitrarily close to the nonlinear Dvoretzky phase transition at distortion 2, we thus obtain a much simpler probabilistic proof of the main result of Bartel, Linial, Mendel, and Naor, answering a question from Mendel and Naor, and yielding the best known bounds in the nonlinear Dvoretzky theorem. Our method utilizes a sequence of random scales at which a given metric space is fragmented. As in many previous randomized arguments in embedding theory, these scales are chosen irrespective of the geometry of the metric space in question. We show that our bounds are sharp if one utilizes such a "scale-oblivious" fragmentation procedure.

Affiliated with

Also associated with

No associations

Rating

Scale-oblivious metric fragmentation and the nonlinear Dvoretzky theorem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Scale-oblivious metric fragmentation and the nonlinear Dvoretzky theorem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Scale-oblivious metric fragmentation and the nonlinear Dvoretzky theorem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-316738