Metric distortion between random finite subsets of the interval
Anton Malyshev (Weizmann Institute)
יום שלישי, 9 ביוני, 2015, 10:50 – 12:00, Math -101
תקציר:
Consider a random finite metric space X given by sampling n points in the unit interval uniformly, and a deterministic finite metric space U given by placing n points in the unit interval at uniform distance. With high probability, X will contain some pairs of points at distance roughly 1/n^2, so any bijection from X to U must distort distances by a factor of roughly n. However, with high probability, two of these random spaces, X_1 and X_2, have a bijection which distorts distances by a factor of only about n^(2/3). The exponent of 2/3 is optimal.