Voir la notice de l'article provenant de la source Numdam
For let denote the metric space of all -integrable Borel probability measures on , equipped with the Wasserstein metric . We prove that for every , every and every finite metric space , the metric space embeds into with distortion at most . We show that this is sharp when in the sense that the exponent cannot be replaced by any larger number. In fact, for arbitrarily large there exists an -point metric space such that for every any embedding of the metric space into incurs distortion that is at least a constant multiple of . These statements establish that there exists an Alexandrov space of nonnegative curvature, namely , with respect to which there does not exist a sequence of bounded degree expander graphs. It also follows that does not admit a uniform, coarse, or quasisymmetric embedding into any Banach space of nontrivial type. Links to several longstanding open questions in metric geometry are discussed, including the characterization of subsets of Alexandrov spaces, existence of expanders, the universality problem for , and the metric cotype dichotomy problem.
Pour notons l'espace métrique des mesures de probabilité -intégrables sur , muni de la -métrique de Wasserstein . Nous montrons que pour tout , tout et tout espace métrique fini , l'espace métrique se plonge dans avec distortion au plus . Nous montrons que cela est optimal quand au sens où l'exposant ne peut pas être augmenté. En fait pour assez grand il existe un espace métrique à points tel que pour tout tout plongement de l'espace métrique dans a une distortion au moins égale à un multiple par une constante de . Ces résultats impliquent qu'il existe un espace d'Alexandrov de courbure positive, à savoir , vis- à-vis duquel il n'existe pas de suite de graphes expanseurs de degré borné. Il en résulte aussi que n'admet pas de plongement uniforme, grossier ou quasisymétrique dans un espace de Banach de type non trivial. Nous discutons le lien avec plusieurs questions ouvertes depuis longtemps en géométrie des espaces métriques, dont la caractérisation des sous-ensembles des espaces d'Alexandrov, l'existence d'expandeurs, le problème d'universalité pour , et le problème de dichotomie pour le cotype métrique.
@article{ASENS_2018__51_3_657_0, author = {Andoni, Alexandr and Naor, Assaf and Neiman, Ofer}, title = {Snowflake universality of {Wasserstein} spaces}, journal = {Annales scientifiques de l'\'Ecole Normale Sup\'erieure}, pages = {657--700}, publisher = {Soci\'et\'e Math\'ematique de France. Tous droits r\'eserv\'es}, volume = {Ser. 4, 51}, number = {3}, year = {2018}, doi = {10.24033/asens.2363}, mrnumber = {3831034}, language = {en}, url = {http://geodesic.mathdoc.fr/articles/10.24033/asens.2363/} }
TY - JOUR AU - Andoni, Alexandr AU - Naor, Assaf AU - Neiman, Ofer TI - Snowflake universality of Wasserstein spaces JO - Annales scientifiques de l'École Normale Supérieure PY - 2018 SP - 657 EP - 700 VL - 51 IS - 3 PB - Société Mathématique de France. Tous droits réservés UR - http://geodesic.mathdoc.fr/articles/10.24033/asens.2363/ DO - 10.24033/asens.2363 LA - en ID - ASENS_2018__51_3_657_0 ER -
%0 Journal Article %A Andoni, Alexandr %A Naor, Assaf %A Neiman, Ofer %T Snowflake universality of Wasserstein spaces %J Annales scientifiques de l'École Normale Supérieure %D 2018 %P 657-700 %V 51 %N 3 %I Société Mathématique de France. Tous droits réservés %U http://geodesic.mathdoc.fr/articles/10.24033/asens.2363/ %R 10.24033/asens.2363 %G en %F ASENS_2018__51_3_657_0
Andoni, Alexandr; Naor, Assaf; Neiman, Ofer. Snowflake universality of Wasserstein spaces. Annales scientifiques de l'École Normale Supérieure, Série 4, Tome 51 (2018) no. 3, pp. 657-700. doi : 10.24033/asens.2363. http://geodesic.mathdoc.fr/articles/10.24033/asens.2363/
Alexandrov meets Kirszbraun, Proceedings of the Gökova Geometry-Topology Conference 2010, Int. Press, Somerville, MA (2011), pp. 88-109 | MR | Zbl
On the bi-Lipschitz structure of Wasserstein spaces (2015) (preprint)
Impossibility of Sketching of the 3D Transportation Metric with Quadratic Cost, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016) (Chatzigiannakis, I.; Mitzenmacher, M.; Sangiorgi, D., eds.) (Leibniz International Proceedings in Informatics (LIPIcs)), Volume 55 (2016), p. 83:1-83:14 | MR
The wreath product of with has Hilbert compression exponent , Proc. Amer. Math. Soc., Volume 137 (2009), pp. 85-90 (ISSN: 0002-9939) | MR | Zbl | DOI
The boundary correspondence under quasiconformal mappings, Acta Math., Volume 96 (1956), pp. 125-142 (ISSN: 0001-5962) | MR | Zbl | DOI
Markov chains, Riesz transforms and Lipschitz maps, Geom. Funct. Anal., Volume 2 (1992), pp. 137-172 (ISSN: 1016-443X) | MR | Zbl | DOI
, 37th Annual Symposium on Foundations of Computer Science (Burlington, VT, 1996), IEEE Comput. Soc. Press, Los Alamitos, CA, 1996, pp. 184-193 | DOI | MR
Ptolemaic spaces and CAT(0), Glasg. Math. J., Volume 51 (2009), pp. 301-314 (ISSN: 0017-0895) | MR | Zbl | DOI
A. D. Aleksandrov spaces with curvatures bounded below, Uspekhi Mat. Nauk, Volume 47 (1992), p. 3-51, 222 (ISSN: 0042-1316) | MR | Zbl | DOI
, Grundl. math. Wiss., 319, Springer, Berlin, 1999, 643 pages (ISBN: 3-540-64324-9) | MR | Zbl | DOI
On metric Ramsey-type phenomena, Ann. of Math., Volume 162 (2005), pp. 643-709 (ISSN: 0003-486X) | MR | Zbl | DOI
Dichotomie du cotype pour les espaces invariants, C. R. Acad. Sci. Paris Sér. I Math., Volume 300 (1985), pp. 263-266 (ISSN: 0249-6291) | MR | Zbl
On a distance characterization of A. D. Aleksandrov spaces of nonpositive curvature, Dokl. Akad. Nauk, Volume 414 (2007), pp. 10-12 (ISSN: 0869-5652) | MR | Zbl | DOI
Quasilinearization and curvature of Aleksandrov spaces, Geom. Dedicata, Volume 133 (2008), pp. 195-218 (ISSN: 0046-5755) | MR | Zbl | DOI
Locally decodable codes and the failure of cotype for projective tensor products, Electron. Res. Announc. Math. Sci., Volume 19 (2012), pp. 120-130 (ISSN: 1935-9179) | MR | Zbl | DOI
New Banach space properties of the disc algebra and , Acta Math., Volume 152 (1984), pp. 1-48 (ISSN: 0001-5962) | MR | Zbl | DOI
On Lipschitz embedding of finite metric spaces in Hilbert space, Israel J. Math., Volume 52 (1985), pp. 46-52 (ISSN: 0021-2172) | MR | Zbl | DOI
The metrical interpretation of superreflexivity in Banach spaces, Israel J. Math., Volume 56 (1986), pp. 222-230 (ISSN: 0021-2172) | MR | Zbl | DOI
, Academic Press Inc., New York, N. Y., 1955, 422 pages |, Classification and dissimilarity analysis (Lect. Notes Stat.), Volume 93, Springer, New York, 1994, pp. 5-65 | MR | Zbl | DOI
Markov type and threshold embeddings, Geom. Funct. Anal., Volume 23 (2013), pp. 1207-1229 | MR | Zbl | DOI
, Oxford Lecture Series in Mathematics and its Applications, 7, The Clarendon Press, Oxford Univ. Press, New York, 1997, 212 pages (ISBN: 0-19-850166-8) | MR | Zbl
On the nonexistence of uniform homeomorphisms between -spaces, Ark. Mat., Volume 8 (1969), pp. 103-105 (ISSN: 0004-2080) | MR | Zbl | DOI
Uniform homeomorphisms between Banach spaces, Séminaire Maurey-Schwartz (1975–1976), Espaces, , applications radonifiantes et géométrie des espaces de Banach, Exp. No. 18, Centre Math., École polytech., Palaiseau (1976) | MR | Zbl | mathdoc-id
Nonpositive curvature and the Ptolemy inequality, Int. Math. Res. Not., Volume 2007 (2007) (ISSN: 1073-7928) | MR | Zbl | DOI
Hyperbolicity, -spaces and the Ptolemy inequality, Math. Ann., Volume 350 (2011), pp. 339-356 (ISSN: 0025-5831) | MR | Zbl | DOI
, Cambridge Univ. Press, Cambridge, 2007, 335 pages (ISBN: 978-0-521-69973-0) |Lipschitz-free Banach spaces, Studia Math., Volume 159 (2003), pp. 121-141 (ISSN: 0039-3223) | MR | Zbl | DOI
-spaces: construction and concentration, Zap. Nauchn. Sem. S. Peterburg. Otdel. Mat. Inst. Steklov. (POMI), Volume 280 (2001) (ISSN: 0373-2703) | MR | Zbl | DOI
Random walk in random groups, Geom. Funct. Anal., Volume 13 (2003), pp. 73-146 (ISSN: 1016-443X) | MR | Zbl | DOI
Filling Riemannian manifolds, J. Differential Geom., Volume 18 (1983), pp. 1-147 http://projecteuclid.org/euclid.jdg/1214509283 (ISSN: 0022-040X) | MR | Zbl
, Geometric group theory, vol. 2 (Sussex, 1991) (London Math. Soc. Lecture Note Ser.), Volume 182, Cambridge Univ. Press, Cambridge, 1993, pp. 1-295 | MR | Zbl
, Progress in Math., 152, Birkhäuser, 1999, 585 pages (ISBN: 0-8176-3898-9) | MR | Zbl
Expander graphs and their applications, Bull. Amer. Math. Soc., Volume 43 (2006), pp. 439-561 (ISSN: 0273-0979) | MR | Zbl | DOI
Fast construction of nets in low-dimensional metrics and their applications, SIAM J. Comput., Volume 35 (2006), pp. 1148-1184 (ISSN: 0097-5397) | MR | Zbl | DOI
, Lectures in Mathematics ETH Zürich, Birkhäuser, 1997, 108 pages (ISBN: 3-7643-5736-3) | MR | Zbl | DOI
The ptolemaic inequality in Hilbert geometries, Pacific J. Math., Volume 21 (1967), pp. 293-301 http://projecteuclid.org/euclid.pjm/1102992501 (ISSN: 0030-8730) | MR | Zbl | DOI
Rigidity of quasi-isometries for symmetric spaces and Euclidean buildings, Publ. Math. IHÉS, Volume 86 (1997), pp. 115-197 (ISSN: 0073-8301) | MR | Zbl | mathdoc-id | DOI
Nonembeddability theorems via Fourier analysis, Math. Ann., Volume 334 (2006), pp. 821-852 (ISSN: 0025-5831) | MR | Zbl | DOI
Absolutely summing operators and translation-invariant spaces of functions on compact abelian groups, Math. Nachr., Volume 94 (1980), pp. 303-340 (ISSN: 0025-584X) | MR | Zbl | DOI
Plane with -weighted metric not bi-Lipschitz embeddable to , Bull. London Math. Soc., Volume 34 (2002), pp. 667-676 (ISSN: 0024-6093) | MR | Zbl | DOI
Un renforcement de la propriété (T), Duke Math. J., Volume 143 (2008), pp. 559-602 (ISSN: 0012-7094) | MR | Zbl | DOI
Propriété (T) renforcée banachique et transformation de Fourier rapide, J. Topol. Anal., Volume 1 (2009), pp. 191-206 (ISSN: 1793-5253) | MR | Zbl | DOI
Strong Banach property (T) for simple algebraic groups of higher rank, J. Topol. Anal., Volume 6 (2014), pp. 75-105 (ISSN: 1793-5253) | MR | Zbl | DOI
Girth and Euclidean distortion, Geom. Funct. Anal., Volume 12 (2002), pp. 380-394 (ISSN: 1016-443X) | MR | Zbl | DOI
Metric structures in : dimension, snowflakes, and average distortion, European J. Combin., Volume 26 (2005), pp. 1180-1190 (ISSN: 0195-6698) | MR | Zbl | DOI
Embedding the diamond graph in and dimension reduction in , Geom. Funct. Anal., Volume 14 (2004), pp. 745-747 (ISSN: 1016-443X) | MR | Zbl | DOI
Bilipschitz embeddings of metric spaces into space forms, Geom. Dedicata, Volume 87 (2001), pp. 285-307 (ISSN: 0046-5755) | MR | Zbl | DOI
Curvature bounded below: a definition a la Berg-Nikolaev, Electron. Res. Announc. Math. Sci., Volume 17 (2010), pp. 122-124 (ISSN: 1935-9179) | MR | Zbl | DOI
Extensions of Lipschitz maps into Hadamard spaces, Geom. Funct. Anal., Volume 10 (2000), pp. 1527-1553 (ISSN: 1016-443X) | MR | Zbl | DOI
Kirszbraun's theorem and metric spaces of bounded curvature, Geom. Funct. Anal., Volume 7 (1997), pp. 535-560 (ISSN: 1016-443X) | MR | Zbl | DOI
Ricci curvature for metric-measure spaces via optimal transport, Ann. of Math., Volume 169 (2009), pp. 903-991 (ISSN: 0003-486X) | MR | Zbl | DOI
, Graduate Texts in Math., 212, Springer, 2002 | MR | Zbl
On embedding expanders into spaces, Israel J. Math., Volume 102 (1997), pp. 189-197 (ISSN: 0021-2172) | MR | Zbl | DOI
Type, cotype and -convexity, Handbook of the geometry of Banach spaces, Volume 2, North-Holland (2003), pp. 1299-1332 | MR | Zbl | DOI
, Limits of graphs in group theory and computer science, EPFL Press, Lausanne, 2009, pp. 59-76 | MR | Zbl
Sphere equivalence, Banach expanders, and extrapolation, Int. Math. Res. Not., Volume 2015 (2015), pp. 4372-4391 (ISSN: 1073-7928) | DOI | MR
A note on dichotomies for metric transforms (preprint arXiv:1102.1800 )
Metric cotype, Ann. of Math., Volume 168 (2008), pp. 247-298 (ISSN: 0003-486X) | MR | Zbl | DOI
Maximum gradient embeddings and monotone clustering, Combinatorica, Volume 30 (2010), pp. 581-615 (ISSN: 0209-9683) | MR | Zbl | DOI
Markov convexity and local rigidity of distorted metrics, J. Eur. Math. Soc. (JEMS), Volume 15 (2013), pp. 287-337 (ISSN: 1435-9855) | MR | Zbl | DOI
Nonlinear spectral calculus and super-expanders, Publ. Math. IHÉS, Volume 119 (2014), pp. 1-95 (ISSN: 0073-8301) | MR | Zbl | DOI
Expanders with respect to Hadamard spaces and random graphs, Duke Math. J., Volume 164 (2015), pp. 1471-1548 (ISSN: 0012-7094) | DOI | MR
Caractérisation d'une classe d'espaces de Banach par des propriétés de séries aléatoires vectorielles, C. R. Acad. Sci. Paris, Volume 277 (1973), p. A687-A690 | MR | Zbl
A phase transition phenomenon between the isometric and isomorphic extension problems for Hölder functions between spaces, Mathematika, Volume 48 (2001), pp. 253-271 (ISSN: 0025-5793) | MR | Zbl | DOI
, Metric and differential geometry (Progr. Math.), Volume 297, Birkhäuser, 2012, pp. 175-178 | MR | Zbl | DOI
An introduction to the Ribe program, Jpn. J. Math., Volume 7 (2012), pp. 167-233 (ISSN: 0289-2316) | MR | Zbl | DOI
Comparison of metric spectral gaps, Anal. Geom. Metr. Spaces, Volume 2 (2014), pp. 1-52 (ISSN: 2299-3274) | MR | Zbl | DOI
Poincaré inequalities and rigidity for actions on Banach spaces, J. Eur. Math. Soc. (JEMS), Volume 17 (2015), pp. 689-709 (ISSN: 1435-9855) | DOI | MR
Embeddings of discrete groups and the speed of random walks, Int. Math. Res. Not., Volume 2008 (2008) (ISSN: 1073-7928) | MR | Zbl | DOI
compression, traveling salesmen, and stable walks, Duke Math. J., Volume 157 (2011), pp. 53-108 (ISSN: 0012-7094) | MR | Zbl | DOI
Markov chains in smooth Banach spaces and Gromov-hyperbolic metric spaces, Duke Math. J., Volume 134 (2006), pp. 165-197 (ISSN: 0012-7094) | MR | Zbl | DOI
A lower bound on the distortion of embedding planar metrics into Euclidean space, Discrete Comput. Geom., Volume 29 (2003), pp. 77-81 (ISSN: 0179-5376) | MR | Zbl | DOI
Remarks on non linear type and Pisier's inequality, J. reine angew. Math., Volume 552 (2002), pp. 213-236 (ISSN: 0075-4102) | MR | Zbl | DOI
Planar earthmover is not in , SIAM J. Comput., Volume 37 (2007), pp. 804-826 (ISSN: 0097-5397) | MR | Zbl | DOI
Poincaré inequalities, embeddings, and wild groups, Compos. Math., Volume 147 (2011), pp. 1546-1572 (ISSN: 0010-437X) | MR | Zbl | DOI
Markov type of Alexandrov spaces of non-negative curvature, Mathematika, Volume 55 (2009), pp. 177-189 (ISSN: 0025-5793) | MR | Zbl | DOI
A note on Markov type constants, Arch. Math. (Basel), Volume 92 (2009), pp. 80-88 (ISSN: 0003-889X) | MR | Zbl | DOI
The geometry of dissipative evolution equations: the porous medium equation, Comm. Partial Differential Equations, Volume 26 (2001), pp. 101-174 (ISSN: 0360-5302) | MR | Zbl | DOI
A note on non-amenability of for , Internat. J. Math., Volume 15 (2004), pp. 557-565 (ISSN: 0129-167X) | MR | Zbl | DOI
, Conference Board of the Mathematical Sciences Regional Conference Series in Mathematics, 30, Amer. Math. Soc., 1977 | MR | Zbl
, Séminaire sur la Géométrie des Espaces de Banach (1977–1978), exp. no 14, École polytech., Palaiseau, 1978 | MR | Zbl | mathdoc-id
Factorization of operator valued analytic functions, Adv. Math., Volume 93 (1992), pp. 61-125 (ISSN: 0001-8708) | MR | Zbl | DOI
Non-expansive maps in a space of curvature no greater than , Sibirsk. Mat. Ž., Volume 9 (1968), pp. 918-927 (ISSN: 0037-4474) | MR
On uniformly homeomorphic normed spaces, Ark. Mat., Volume 14 (1976), pp. 237-244 (ISSN: 0004-2080) | MR | Zbl | DOI
, Probability and its Applications (New York), Springer, New York, 1998, 430 pages (ISBN: 0-387-98352-X) | MR | Zbl
An alternative proof of Berg and Nikolaev's characterization of -spaces via quadrilateral inequality, Arch. Math. (Basel), Volume 93 (2009), pp. 487-490 (ISSN: 0003-889X) | MR | Zbl | DOI
Metric spaces and positive definite functions, Trans. Amer. Math. Soc., Volume 44 (1938), pp. 522-536 | MR | JFM | DOI
, Heat kernels and analysis on manifolds, graphs, and metric spaces (Paris, 2002) (Contemp. Math.), Volume 338, Amer. Math. Soc., Providence, RI, 2003, pp. 357-390 | MR | Zbl | DOI
On the geometry of metric measure spaces. I, Acta Math., Volume 196 (2006), pp. 65-131 (ISSN: 0001-5962) | MR | Zbl | DOI
Metric spaces of lower bounded curvature, Exposition. Math., Volume 17 (1999), pp. 35-47 (ISSN: 0723-0869) | MR | Zbl
Length inequalities in trees and CAT(0) spaces (2014) ( http://mathoverflow.net/q/163706 )
The moduli of smoothness and convexity and the Rademacher averages of trace classes , Studia Math., Volume 50 (1974), pp. 163-182 (ISSN: 0039-3223) | MR | Zbl
Quasisymmetric embeddings of metric spaces, Ann. Acad. Sci. Fenn. Ser. A I Math., Volume 5 (1980), pp. 97-114 (ISSN: 0066-1953) | MR | Zbl | DOI
Une remarque sur les ensembles de Helson, Duke Math. J., Volume 43 (1976), pp. 387-390 http://projecteuclid.org/euclid.dmj/1077311648 (ISSN: 0012-7094) | MR | Zbl | DOI
, Graduate Studies in Math., 58, Amer. Math. Soc., Providence, RI, 2003, 370 pages (ISBN: 0-8218-3312-X) | MR | Zbl | DOI
, Cambridge Studies in Advanced Math., 25, Cambridge Univ. Press, Cambridge, 1991, 382 pages (ISBN: 0-521-35618-0) | MR | Zbl | DOI
, Ergebn. Math. Grenzg., 84, Springer, 1975, 108 pages | MR | Zbl
A rigidity theorem in Alexandrov spaces with lower curvature bound, Math. Ann., Volume 353 (2012), pp. 305-331 (ISSN: 0025-5831) | MR | Zbl | DOI
Cité par Sources :