6. Transportation Cost and Wasserstein Spaces
-
Problem 6.1.
[Mikhail Ostrovskii] Does there exist a function $f: [0,\infty) \to [0,\infty)$ such that, for every finite metric space $M$, the distortion of $M$ into convex combinations of dominating tree metrics is bounded by $f(c_1({\rm TC}(M)))$? -
Problem 6.2.
[Erik Waingarten] Let $M = \{1,\dots \Delta\}^d$ equipped with the $\ell_1$ or $\ell_2$ metric. Let $Y$ the subset of $W_1(M)$ consisting of uniform distributions over $s$-point subsets of $M$. What are the asymptotics of $c_1(Y)$ in terms of $\Delta,d,s$? Can $c_1(Y)$ be bounded by a function of $s$ only?-
Remark. Using convex combinations of dominating tree metrics, it holds that $c_1(Y) \leq c_1(W_1(M)) = O(d\log (\Delta))$. Results of Andoni-Indyk-Krauthgamer give different upper bounds. For example, for the $\ell_1$-metric, they obtain $c_1(Y) = O(\log(s)\log(d\Delta))$.
-
-
Problem 6.3.
[Mikhail Ostrovskii] Let $\{G_n\}_{n=1}^\infty$ be a sequence of bounded degree expanders. Does the $\ell_2$-sum $(\oplus_n \mathrm{TC}(G_n))_2$ have trivial cotype? -
Problem 6.4.
[Assaf Naor] Let $\{1,\dots n\}^d$ denote the $d$-dimensional grid graph of side length $n-1$. What are the asymptotics of $c_1({\rm TC}(\{1,\dots n\}^d))$ for $d \geq 2$?-
Remark. [org.aimpl.user:cgartla1@charlotte.edu] The preprint https://arxiv.org/abs/2602.19434 establishes $c_1({\rm TC}(\{1,\dots n\}^d)) = \Theta(d\log n)$.
-
Cite this as: AimPL: Metric embeddings, available at http://aimpl.org/metricembeddings.