Embedding metric spaces into normed spaces and estimates of metric capacity

Let be an arbitrary real normed space of finite dimension d ≥ 2. We define the metric capacity of as the maximal such that every m-point metric space is isometric to some subset of (with metric induced by ). We obtain that the metric capacity of lies in the range from 3 to , where the lower bound is sharp for all d, and the upper bound is shown to be sharp for d ∈ {2, 3}. Thus, the unknown sharp upper bound is asymptotically linear, since it lies in the range from d + 2 to . Research supported by the German Research Foundation, Project AV 85/1-1.     

Embedding metric spaces into normed spaces and estimates of metric capacity

Let M^d{\cal M}^d be an arbitrary real normed space of finite dimension d ≥ 2. We define the metric capacity of M^d{\cal M}^d as the maximal m ? \Bbb Nm \in {\Bbb N} such that every m-point metric space is isometric to some subset of M^d{\cal M}^d (with metric induced by M^d{\cal M}^d ). We obtain that the metric capacity of M^d{\cal M}^d lies in the range from 3 to ë\frac32d û+1\left\lfloor\frac{3}{2}d\right\rfloor+1 , where the lower bound is sharp for all d, and the upper bound is shown to be sharp for d ∈ {2, 3}. Thus, the unknown sharp upper bound is asymptotically linear, since it lies in the range from d + 2 to ë\frac32d û+1\left\lfloor\frac{3}{2}d\right\rfloor+1 .     

On lipschitz embedding of finite metric spaces in Hilbert space

It is shown that anyn point metric space is up to logn lipeomorphic to a subset of Hilbert space. We also exhibit an example of ann point metric space which cannot be embedded in Hilbert space with distortion less than (logn)/(log logn), showing that the positive result is essentially best possible. The methods used are of probabilistic nature. For instance, to construct our example, we make use of random graphs.     

On classification of finite metric spaces

Translated from Matematicheskie Zametki, Vol. 56, No. 4, pp. 48–58, October, 1994.     

The metric gradient in normed linear spaces

Summary In this paper we give a definition for the gradient of a functional defined on a normed linear space which in the case of Hilbert space reduces to the usual definition. We also establish some interesting properties of the gradient which allow us to extend the well-known theorem of Curry to a large class of normed linear spaces.A part of this research was sponsored by the U.S. Army under contract No. DA-31-124-ARO-D-462.     

On hilbertian subsets of finite metric spaces

The following result is proved: For everyε>0 there is aC(ε)>0 such that every finite metric space (X, d) contains a subsetY such that |Y|≧C(ε)log|X| and (Y, d _Y) embeds (1 +ε)-isomorphically into the Hilbert spacel ₂. The authors are grateful to Haim Wolfson for some discussions related to the content of this paper.     

Almost isometric embedding between metric spaces

We investigate the relations ofalmost isometric embedding and ofalmost isometry between metric spaces. These relations have several appealing features. For example, all isomorphism types of countable dense subsets of ∝ form exactly one almostisometry class, and similarly with countable dense subsets of Uryson's universal separable metric spaceU. We investigate geometric, set-theoretic and model-theoretic aspects of almost isometry and of almost isometric embedding. The main results show that almost isometric embeddability behaves in the category ofseparable metric spaces differently than in the category of general metric spaces. While in the category of general metric spaces the behavior of universality resembles that in the category of linear orderings —namely, no universal structure can exist on a regular λ > ℵ₁ below the continuum—in the category of separable metric spaces universality behaves more like that in the category of graphs, that is, a small number of metric separable metric spaces on an uncountable regular λ<2^ℵ ₀ may consistently almost isometrically embed all separable metric spaces on λ. Research of the first author was supported by an Israeli Science foundation grant no. 177/01. Research of the second author was supported by the United States-Israel Binational Science Foundation. Publication 827.     

Low distortion embeddings of some metric graphs into Banach spaces

We give a simple example of a countable metric graph M such that M Lipschitz embeds with distortion strictly less than 2 into a Banach space X only if X contains an isomorphic copy of l ₁. Further we show that, for each ordinal α < ω ₁, the space C([0, ω ^α ]) does not Lipschitz embed into C(K) with distortion strictly less than 2 unless K ^(α) ≠ 0. Also \(C\left( {\left[ {0,{\omega ^{{\omega ^\alpha }}}} \right]} \right)\) does not Lipschitz embed into a Banach space X with distortion strictly less than 2 unless Sz(X) ≥ ω ^α+1.     

Two observations regarding embedding subsets of Euclidean spaces in normed spaces

This paper contains two results concerning linear embeddings of subsets of Euclidean space in low-dimensional normed spaces. The first is an improvement of the known dependence on ? in Dvoretzky's theorem from order of ?² to order of ? (except for log factors). The second is a joint generalization of (Milman's version of) Dvoretzky's theorem and (a recent generalization by Klartag and Mendelson of) the Johnson-Lindenstrauss Lemma.     

On the probability that finite spaces with random distances are metric spaces

For a set of 3 or 4 points we compute the exact probability that, after assigning the distances between these points uniformly at random from the set 1,…,n , the space obtained is metric. The corresponding results for random real distances follow easily. We also prove estimates for the general case of a finite set of points with uniformly random real distances.     

On embedding expanders into ℓ p spaces

In this note we show that the minimum distortion required to embed alln-point metric spaces into the Banach space ℓ _p is between (c ₁/p) logn and (c ₂/p) logn, wherec ₂>c ₁>0 are absolute constants and 1≤p<logn. The lower bound is obtained by a generalization of a method of Linial et al. [LLR95], by showing that constant-degree expanders (considered as metric spaces) cannot be embedded any better. Research supported by Czech Republic Grant GAČR 201/94/2167 and Charles University grants No. 351 and 361.     

An embedding theorem for finite planar spaces

LetS be a finite planar space such that any two distinct planes intersect in a line. We show thatk≤n ²+1 for anyk-cap ofS, wheren is the order ofS. Moreover, if a (n ²+1)-cap exists inS, a necessary and sufficient condition is provided forS to be embeddable in a 3-dimensional projective space. Work supported by the National Research Project “Strutture geometriche, Combinatoria e loro applicazioni” of the italian M.U.R.S.T.     

A constructive and functorial embedding of locally compact metric spaces into locales

The paper establishes, within constructive mathematics, a full and faithful functor M from the category of locally compact metric spaces and continuous functions into the category of formal topologies (or equivalently locales). The functor preserves finite products, and moreover satisfies f?g if, and only if, M(f)?M(g) for continuous . This makes it possible to transfer results between Bishop's constructive theory of metric spaces and constructive locale theory.     

Convexity in finite metric spaces

A subsetS of a metric space (X,d) is calledd-convex if for any pair of pointsx,y S each pointz X withd(x,z) +d(z,y) =d(x,y) belongs toS. We give some results and open questions concerning isometric and convexity-preserving embeddings of finite metric spaces into standard spaces and the number ofd-convex sets of a finite metric space.     

On the gap of finite metric spaces of p-negative type

Let $(X\text{,}d)$ be a metric space of p-negative type. Recently I. Doust and A. Weston introduced a quantification of the p-negative type property, the so called gap $\mathrm{\Gamma }$ of X. This paper gives some formulas for the gap $\mathrm{\Gamma }$ of a finite metric space of strict p-negative type and applies them to evaluate $\mathrm{\Gamma }$ for some concrete finite metric spaces.     

On optimal realizations of finite metric spaces by graphs

Graph realizations of finite metric spaces have widespread applications, for example, in biology, economics, and information theory. The main results of this paper are:

1. Finding optimal realizations of integral metrics (which means all distances are integral) is NP-complete.
2. There exist metric spaces with a continuum of optimal realizations.

Furthermore, two conditions necessary for a weighted graph to be an optimal realization are given and an extremal problem arising in connection with the realization problem is investigated.     

Fixed and periodic points in the probabilistic normed and metric spaces

In this paper, a fixed point theorem is proved, i.e., if A is a C-contraction in the Menger space (S, F) and E  S be such that is compact, then A has a fixed point. In addition, under the same condition, the existence of a periodic point of A is proved. Finally, a fixed point theorem in probabilistic normed spaces is proved.     

Linear operators in finite dimensional probabilistic normed spaces

In this paper, we consider strongly bounded linear operators on a finite dimensional probabilistic normed space and define the topological isomorphism between probabilistic normed spaces. Then we prove that every finite dimensional probabilistic normed space which is a topological vector space is complete.