The structure of a typical metric space

Seminar
Speaker
Ron Peled
Date
10/12/2013 - 14:45Add to Calendar 2013-12-10 14:45:00 2013-12-10 14:45:00 The structure of a typical metric space ~~How does a uniformly chosen metric space on n points look like? To formalize this we consider the set of all metric spaces on n points whose diameter is at most 2. Viewing every metric space as a vector of distances, this set becomes a convex polytope in R^{n choose 2} - the metric polytope. A uniformly random metric space is then a space chosen according to the normalized Lebesgue measure on this polytope. It is simple to see that the metric polytope contains the cube [1,2]^{n choose 2}. Our main result is that it does not contain much more. Precisely, that a random metric space is very rigid, having all distances in an interval of the form [1 - n^{-a}, 2] with high probability. We consider three approaches to the problem, with varying degrees of accuracy, based on exchangeability, the Szemerédi regularity lemma and entropy techniques. Joint work with Gady Kozma, Tom Meyerovitch and Wojciech Samotij. אוניברסיטת בר-אילן - Department of Mathematics mathoffice@math.biu.ac.il Asia/Jerusalem public
Abstract

~~How does a uniformly chosen metric space on n points look like? To formalize this we consider the set of all metric spaces on n points whose diameter is at most 2. Viewing every metric space as a vector of distances, this set becomes a convex polytope in R^{n choose 2} - the metric polytope. A uniformly random metric space is then a space chosen according to the normalized Lebesgue measure on this polytope. It is simple to see that the metric polytope contains the cube [1,2]^{n choose 2}. Our main result is that it does not contain much more. Precisely, that a random metric space is very rigid, having all distances in an interval of the form [1 - n^{-a}, 2] with high probability. We consider three approaches to the problem, with varying degrees of accuracy, based on exchangeability, the Szemerédi regularity lemma and entropy techniques.

Joint work with Gady Kozma, Tom Meyerovitch and Wojciech Samotij.

Last Updated Date : 08/12/2013