$L_1$-distortion of Wasserstein metrics: a tale of two dimensions

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}^{\mathrm{\infty }}$ is a sequence of graphs whose isoperimetric dimension and Lipschitz-spectral dimension equal a common number $\delta \in [2,\mathrm{\infty })$, then the 1-Wasserstein metric over $G_n$ has $L_1$-distortion bounded below by a constant multiple of $(\log \mathrm{\mid }{G}_n\mathrm{\mid }{)}^{\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}^{\mathrm{\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 \mathrm{\mid }{\mathsf{D}}_n\mathrm{\mid }}$. 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.