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.     

Euclidean quotients of finite metric spaces

This paper is devoted to the study of quotients of finite metric spaces. The basic type of question we ask is: Given a finite metric space M and α?1, what is the largest quotient of (a subset of) M which well embeds into Hilbert space. We obtain asymptotically tight bounds for these questions, and prove that they exhibit phase transitions. We also study the analogous problem for embeddings into ?_p, and the particular case of the hypercube.     

Euclidean embeddings of finite metric spaces

This is a brief survey on Euclidean embeddings of finite metric spaces, focusing on the power transform metric with many examples. Some old results are presented in slightly improved forms, and the last section contains a few new results. Proofs are given if they are elementary and not too long. Several problems and conjectures are also given.     

Isometric embeddings of finite metric spaces

It is proved that there exists a metric on a Cantor set such that any finite metric space whose diameter does not exceed 1 and the number of points does not exceed n can be isometrically embedded into it. It is also proved that for any m, n ∈ N there exists a Cantor set in R^m that isometrically contains all finite metric spaces which can be embedded into R^m, contain at most n points, and have the diameter at most 1. The latter result is proved for a wide class of metrics on R^m and, in particular, for the Euclidean metric.     

On classification of finite metric spaces

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

Main metric invariants of finite metric spaces. II

In the present paper we obtain new main metric invariants of finite metric spaces. These invariants can be used for classification of the finite metric spaces and their recognition.     

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.     

Main Metric invariants of finite metric spaces. III

We find new main metric invariants of finite metric spaces. All these invariants are allotted to three sets.     

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.     

On the distortion required for embedding finite metric spaces into normed spaces

We investigate the minimum dimensionk such that anyn-point metric spaceM can beD-embedded into somek-dimensional normed spaceX (possibly depending onM), that is, there exists a mappingf: M→X with $$\frac{1}{D}dist_M (x,y) \leqslant \left| {f(x) - f(y)} \right| \leqslant dist_M (x,y) for any$$ Extending a technique of Arias-de-Reyna and Rodríguez-Piazza, we prove that, for any fixedD≥1,k≥c(D)n ^1/2D for somec(D)>0. For aD-embedding of alln-point metric spaces into the samek-dimensional normed spaceX we find an upper boundk≤12Dn ^1/[(D+1)/2]lnn (using thel _∞ ^k space forX), and a lower bound showing that the exponent ofn cannot be decreased at least forD?[1,7)∪[9,11), thus the exponent is in fact a jumping function of the (continuously varied) parameterD.     

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.     

The additivity criterion for finite metric spaces and minimal fillings

A new additivity criterion for finite metric spaces is obtained. The criterion is based on properties of minimal fillings in the sense of M. Gromov     

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 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.     

A Federer-style characterization of sets of finite perimeter on metric spaces

In the setting of a metric space equipped with a doubling measure that supports a Poincaré inequality, we show that a set E is of finite perimeter if and only if \({\mathcal {H}}(\partial ^1 I_E)<\infty \), that is, if and only if the codimension one Hausdorff measure of the 1-fine boundary of the set’s measure theoretic interior \(I_E\) is finite. To obtain the necessity of the above condition, we prove a suitable characterization of the 1-fine boundary, analogously to what is known in the case \(p>1\), and apply a quasicontinuity-type result for \(\mathrm {BV}\) functions proved in the metric setting by Lahti and Shanmugalingam (J Math Pures Appl (9) 107(2):150–182, 2017). To obtain the sufficiency, we generalize further results of fine potential theory from the case \(p>1\) to the case \(p=1\), including weak analogs of a Cartan property for solutions of obstacle problems, and of the Choquet property for finely open sets.