Embeddings of Gromov hyperbolic spaces

It is shown that a Gromov hyperbolic geodesic metric space X with bounded growth at some scale is roughly quasi-isometric to a convex subset of hyperbolic space. If one is allowed to rescale the metric of X by some positive constant, then there is an embedding where distances are distorted by at most an additive constant.?Another embedding theorem states that any -hyperbolic metric space embeds isometrically into a complete geodesic -hyperbolic space.?The relation of a Gromov hyperbolic space to its boundary is further investigated. One of the applications is a characterization of the hyperbolic plane up to rough quasi-isometries. Submitted: October 1998, Revised version: January 1999.     

Realization of Metric Spaces as Inverse Limits, and Bilipschitz Embedding in L 1

We give sufficient conditions for a metric space to bilipschitz embed in L ₁. In particular, if X is a length space and there is a Lipschitz map ${u: X \rightarrow \mathbb R}$ such that for every interval ${I \subset \mathbb R}$ , the connected components of u ^?1(I) have diameter ${\leq {\rm const} \cdot {\rm diam}(I)}$ , then X admits a bilipschitz embedding in L ₁. As a corollary, the Laakso examples, (Geom Funct Anal 10(1):111–123, 2000), bilipschitz embed in L ₁, though they do not embed in any any Banach space with the Radon–Nikodym property (e.g. the space ? ₁ of summable sequences). The spaces appearing the statement of the bilipschitz embedding theorem have an alternate characterization as inverse limits of systems of metric graphs satisfying certain additional conditions. This representation, which may be of independent interest, is the initial part of the proof of the bilipschitz embedding theorem. The rest of the proof uses the combinatorial structure of the inverse system of graphs and a diffusion construction, to produce the embedding in L ₁.     

Products of Hyperbolic Metric Spaces

Let (X _i d _i ), i=1,2, be proper geodesic hyperbolic metric spaces. We give a general construction for a 'hyperbolic product' X ₁× _h X ₂ which is itself a proper geodesic hyperbolic metric space and examine its boundary at infinity.     

Advances in metric embedding theory

Metric Embedding plays an important role in a vast range of application areas such as computer vision, computational biology, machine learning, networking, statistics, and mathematical psychology, to name a few. The mathematical theory of metric embedding is well studied in both pure and applied analysis and has more recently been a source of interest for computer scientists as well. Most of this work is focused on the development of bi-Lipschitz mappings between metric spaces. In this paper we present new concepts in metric embeddings as well as new embedding methods for metric spaces. We focus on finite metric spaces, however some of the concepts and methods are applicable in other settings as well.One of the main cornerstones in finite metric embedding theory is a celebrated theorem of Bourgain which states that every finite metric space on n points embeds in Euclidean space with distortion. Bourgain?s result is best possible when considering the worst case distortion over all pairs of points in the metric space. Yet, it is natural to ask: can an embedding do much better in terms of the average distortion? Indeed, in most practical applications of metric embedding the main criteria for the quality of an embedding is its average distortion over all pairs.In this paper we provide an embedding with constant average distortion for arbitrary metric spaces, while maintaining the same worst case bound provided by Bourgain?s theorem. In fact, our embedding possesses a much stronger property. We define the ?q-distortion of a uniformly distributed pair of points. Our embedding achieves the best possible ?q-distortion for all 1?q?∞simultaneously.The results are based on novel embedding methods which improve on previous methods in another important aspect: the dimension of the host space. The dimension of an embedding is of very high importance in particular in applications and much effort has been invested in analyzing it. However, no previous result improved the bound on the dimension which can be derived from Bourgain?s embedding. Our embedding methods achieve better dimension, and in fact, shed new light on another fundamental question in metric embedding, which is: whether the embedding dimension of a metric space is related to its intrinsic dimension? I.e., whether the dimension in which it can be embedded in some real normed space is related to the intrinsic dimension which is reflected by the inherent geometry of the space, measured by the space?s doubling dimension. The existence of such an embedding was conjectured by Assouad,⁴and was later posed as an open problem in several papers. Our embeddings give the first positive result of this type showing any finite metric space obtains a low distortion (and constant average distortion) embedding in Euclidean space in dimension proportional to its doubling dimension.Underlying our results is a novel embedding method. Probabilistic metric decomposition techniques have played a central role in the field of finite metric embedding in recent years. Here we introduce a novel notion of probabilistic metric decompositions which comes particularly natural in the context of embedding. Our new methodology provides a unified approach to all known results on embedding of arbitrary finite metric spaces. Moreover, as described above, with some additional ideas they allow to get far stronger results.The results presented in this paper⁵have been the basis for further developments both within the field of metric embedding and in other areas such as graph theory, distributed computing and algorithms. We present a comprehensive study of the notions and concepts introduced here and provide additional extensions, related results and some examples of algorithmic applications.     

Embedding Levy families into Banach spaces

We prove that if a metric probability space with a usual concentration property embeds into a finite dimensional Banach space X, then X has a Euclidean subspace of a proportional dimension. In particular this yields a new characterization of weak cotype 2. We also find optimal lower estimates on embeddings of metric spaces with concentration properties into , generalizing estimates of Bourgain—Lindenstrauss—Milman, Carl—Pajor and Gluskin. Submitted: February 2001, Revised: August 2001.     

On the volume functional of compact manifolds with boundary with constant scalar curvature

We study the volume functional on the space of constant scalar curvature metrics with a prescribed boundary metric. We derive a sufficient and necessary condition for a metric to be a critical point, and show that the only domains in space forms, on which the standard metrics are critical points, are geodesic balls. In the zero scalar curvature case, assuming the boundary can be isometrically embedded in the Euclidean space as a compact strictly convex hypersurface, we show that the volume of a critical point is always no less than the Euclidean volume bounded by the isometric embedding of the boundary, and the two volumes are equal if and only if the critical point is isometric to a standard Euclidean ball. We also derive a second variation formula and apply it to show that, on Euclidean balls and “small” hyperbolic and spherical balls in dimensions 3 ≤ n ≤ 5, the standard space form metrics are indeed saddle points for the volume functional.     

Hyperbolic rank and subexponential corank of metric spaces

We introduce a new quasi-isometry invariant corank X of a metric space X called subexponential corank. A metric space X has subexponential corank k if roughly speaking there exists a continuous map , T is a topological space, such that for each the set g ^-1(t) has subexponential growth rate in X and the topological dimension dimT = k is minimal among all such maps. Our main result is the inequality for a large class of metric spaces X including all locally compact Hadamard spaces, where rank _h X is the maximal topological dimension of among all CAT(—1) spaces Y quasi-isometrically embedded into X (the notion introduced by M. Gromov in a slightly stronger form). This proves several properties of rank _h conjectured by Gromov, in particular, that any Riemannian symmetric space X of noncompact type possesses no quasi-isometric embedding of the standard hyperbolic space H ⁿ with . Submitted: February 2001, Revised: October 2001.     

Amenability,locally finite spaces,and bi-lipschitz embeddings

We define the isoperimetric constant for any locally finite metric space and we study the property of having isoperimetric constant equal to zero. This property, called Small Neighborhood property, clearly extends amenability to any locally finite space. Therefore, we start making a comparison between this property and other notions of amenability for locally finite metric spaces that have been proposed by Gromov, Lafontaine and Pansu, by Ceccherini-Silberstein, Grigorchuk and de la Harpe and by Block and Weinberger. We discuss possible applications of the property SN in the study of embedding a metric space into another one. In particular, we propose three results: we prove that a certain class of metric graphs that are isometrically embeddable into Hilbert spaces must have the property SN. We also show, by a simple example, that this result is not true replacing property SN with amenability. As a second result, we prove that many spaces with uniform bounded geometry having a bi-lipschitz embedding into Euclidean spaces must have the property SN. Finally, we prove a Bourgain-like theorem for metric trees: a metric tree with uniform bounded geometry and without property SN does not have bi-lipschitz embeddings into finite-dimensional Hilbert spaces.     

Morrey-Sobolev Spaces on Metric Measure Spaces

In this article, the authors introduce the Newton-Morrey-Sobolev space on a metric measure space (??, d, μ). The embedding of the Newton-Morrey-Sobolev space into the Hölder space is obtained if ?? supports a weak Poincaré inequality and the measure μ is doubling and satisfies a lower bounded condition. Moreover, in the Ahlfors Q-regular case, a Rellich-Kondrachov type embedding theorem is also obtained. Using the Haj?asz gradient, the authors also introduce the Haj?asz-Morrey-Sobolev spaces, and prove that the Newton-Morrey-Sobolev space coincides with the Haj?asz-Morrey-Sobolev space when μ is doubling and ?? supports a weak Poincaré inequality. In particular, on the Euclidean space \({\mathbb R}^n\) , the authors obtain the coincidence among the Newton-Morrey-Sobolev space, the Haj?asz-Morrey-Sobolev space and the classical Morrey-Sobolev space. Finally, when (??, d) is geometrically doubling and μ a non-negative Radon measure, the boundedness of some modified (fractional) maximal operators on modified Morrey spaces is presented; as an application, when μ is doubling and satisfies some measure decay property, the authors further obtain the boundedness of some (fractional) maximal operators on Morrey spaces, Newton-Morrey-Sobolev spaces and Haj?asz-Morrey-Sobolev spaces.     

Reconstruction from Line Integrals in Spaces of Constant Curvature

New reconstruction formula for the line integral transformation in Euclidean spaces is found. The general k-plane integral transform in Euclidean space is related to a totally geodesic integral transform for an arbitrary Riemannian space of constant curvature by means of a factorization property. Duality theorems for the totally geodesic transforms are stated.     

Embedding median algebras in products of trees

We show that a metric median algebra satisfying certain conditions admits a bilipschitz embedding into a finite product of $\mathbb{R }$ -trees. This gives rise to a characterisation of closed connected subalgebras of finite products of complete $\mathbb{R }$ -trees up to bilipschitz equivalence. Spaces of this sort arise as asymptotic cones of coarse median spaces. This applies to a large class of finitely generated groups, via their Cayley graphs. We show that such groups satisfy the rapid decay property. We also recover the result of Behrstock, Dru?u and Sapir, that the asymptotic cone of the mapping class group embeds in a finite product of $\mathbb{R }$ -trees.     

Tilings,packings, coverings,and the approximation of functions

A packing (resp. covering) ? of a normed space X consisting of unit balls is called completely saturated (resp. completely reduced) if no finite set of its members can be replaced by a more numerous (resp. less numerous) set of unit balls of X without losing the packing property (resp. covering property) of ?. We show that a normed space X admits completely saturated packings with disjoint closed unit balls as well as completely reduced coverings with open unit balls, provided that there exists a tiling of X with unit balls. Completely reduced coverings by open balls are of interest in the context of an approximation theory for continuous real‐valued functions that rests on so‐called controllable coverings of compact metric spaces. The close relation between controllable coverings and completely reduced coverings allows an extension of the approximation theory to non‐compact spaces. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

γ-Compact Spaces

Let X be a topological space, denote iA and cA the interior and the closure of A ⊂ X, respectively, and let γ = c o i, or = i o c, or = i o c o i, or = c o i o c. A set A ⊂ X is said to be γ-open [5] iff A ⊂ γ(A). The space X is γ-compact iff each cover of X composed of γ-open sets admits a finite subcover. The purpose of the paper is to investigate some questions concerning γ-compact and related spaces. This revised version was published online in June 2006 with corrections to the Cover Date.     

Projectively equivalent metrics, exact transverse line fields and the geodesic flow on the ellipsoid

We give a new proof of the complete integrability of the geodesic flow on the ellipsoid (in Euclidean, spherical or hyperbolic space). The proof is based on the construction of a metric on the ellipsoid whose non-parameterized geodesics coincide with those of the standard metric. This new metric is induced by the hyperbolic metric inside the ellipsoid (Klein's model).     

Totally geodesic maps into metric spaces

We prove that a totally geodesic map between a Riemannian manifold and a metric space can be represented as the composite of a totally geodesic map from a Riemannian manifold to a Finslerian manifold and a locally isometric embedding between metric spaces. As a corollary, we obtain the homotheticity of a totally geodesic map from an irreducible Riemannian manifold to an Alexandrov space of curvature bounded above. This is a generalization of the case between Riemannian manifolds. Mathematics Subject Classification (2000): 53C20, 53C22, 53C24 Received: 14 March 2002; in final form: 6 May 2002 / / Published online: 24 February 2003     

Polygons in Buildings and their Refined Side Lengths

As in a symmetric space of noncompact type, one can associate to an oriented geodesic segment in a Euclidean building a vector valued length in the Euclidean Weyl chamber Δ _euc . In addition to the metric length it contains information on the direction of the segment. In this paper we study restrictions on the Δ _euc -valued side lengths of polygons in Euclidean buildings. The main result is that for thick Euclidean buildings X the set Pn(X){\mathcal{P}n(X)} of possible Δ _euc -valued side lengths of oriented n-gons depends only on the associated spherical Coxeter complex. We show moreover that it coincides with the space of Δ _euc -valued weights of semistable weighted configurations on the Tits boundary ∂ _Tits X. The side lengths of polygons in symmetric spaces of noncompact type are studied in the related paper [KLM1]. Applications of the geometric results in both papers to algebraic group theory are given in [KLM2].     

Fréchet Embeddings of Negative Type Metrics

We show that every n-point metric of negative type (in particular, every n-point subset of L ₁) admits a Fréchet embedding into Euclidean space with distortion , a result which is tight up to the O(log log n) factor, even for Euclidean metrics. This strengthens our recent work on the Euclidean distortion of metrics of negative into Euclidean space. S. Arora supported by David and Lucile Packard Fellowship and NSF grant CCR-0205594. J.R. Lee supported by NSF grant CCR-0121555, NSF 0514993, NSF 0528414 and an NSF Graduate Research Fellowship.     

On holomorphic immersions into kähler manifolds of constant holomorphic sectional curvature

We study holomorphic immersions f:X →M from a complex manifoldX into a Kähler manifold of constant holomorphic sectional curvatureM, i.e. a complex hyperbolic space form, a complex Euclidean space form, or the complex projective space equipped with the Fubini-Study metric. ForX compact we show that the tangent sequence splits holomorphically if and only iff is a totally geodesic immersion. ForX not necessarily compact we relate an intrinsic cohomological invariantp(X) onX, viz. the invariant defined by Gunning measuring the obstruction to the existence of holomorphic projective connections, to an extrinsic cohomological invariant(f) measuring the obstruction to the holomorphic splitting of the tangent sequence. The two invariantsp(X) and?(f) are related by a linear map on cohomology groups induced by the second fundamental form. In some cases, especially whenX is a complex surface andM is of complex dimension 4, under the assumption thatX admits a holomorphic projective connection we obtain a sufficient condition for the holomorphic splitting of the tangent sequence in terms of the second fundamental form.     

Two Special Simply Connected Spaces of Nonpositive Curvature

We construct two examples of spaces homeomorphic to R ⁿ (n3) each of which has a closed geodesic and admits no isoperimetric inequality. The first is a complete polyhedral metric space of nonpositive curvature, and the second is an incomplete Riemannian space with nonpositive sectional curvatures.     

The metrical interpretation of superreflexivity in banach spaces

The main result is a metrical characterization of superreflexivity in Banach spaces. A Banach spaceX is not superreflexive if and only ifX contains hyperbolic trees as a metric space. The notion of non-linear cotype in discussed.