$L_1$-distortion of Wasserstein metrics: a tale of two dimensions
Institutional Repository Document
Overview
Research
Identity
View All
Overview
abstract
By discretizing an argument of Kislyakov, Naor and Schechtman proved that the 1-Wasserstein metric over the planar grid ${0,1,dots n}^2$ has $L_1$-distortion bounded below by a constant multiple of $sqrt{log n}$. We provide a new "dimensionality" interpretation of Kislyakov's argument, showing that, if ${G_n}_{n=1}^infty$ is a sequence of graphs whose isoperimetric dimension and Lipschitz-spectral dimension equal a common number $delta in [2,infty)$, then the 1-Wasserstein metric over $G_n$ has $L_1$-distortion bounded below by a constant multiple of $(log |G_n|)^{frac{1}{delta}}$. We proceed to compute these dimensions for $oslash$-powers of certain graphs. In particular, we get that the sequence of diamond graphs ${mathsf{D}_n}_{n=1}^infty$ has isoperimetric dimension and Lipschitz-spectral dimension equal to 2, obtaining as a corollary that the 1-Wasserstein metric over $mathsf{D}_n$ has $L_1$-distortion bounded below by a constant multiple of $sqrt{log| mathsf{D}_n|}$. This answers a question of Dilworth, Kutzarova, and Ostrovskii and exhibits only the third sequence of $L_1$-embeddable graphs whose sequence of 1-Wasserstein metrics is not $L_1$-embeddable.
