Metric transforms and Euclidean embeddings

Deza, M.; Maehara, H.

doi:10.1090/S0002-9947-1990-0974513-6

Metric transforms and Euclidean embeddings
HTML articles powered by AMS MathViewer

by M. Deza and H. Maehara PDF

Trans. Amer. Math. Soc. 317 (1990), 661-671 Request permission

Abstract:

It is proved that if $0 \leqslant c \leqslant 0.72/n$ then for any $n$-point metric space $(X,d)$, the metric space $(X,{d^c})$ is isometrically embeddable into a Euclidean space. For $6$-point metric space, $c = \tfrac {1} {2}{\log _2}\tfrac {3} {2}$ is the largest exponent that guarantees the existence of isometric embeddings into a Euclidean space. Such largest exponent is also determined for all $n$-point graphs with "truncated distance".

References

Michael Aschbacher, Pierre Baldi, Eric B. Baum, and Richard M. Wilson, Embeddings of ultrametric spaces in finite-dimensional structures, SIAM J. Algebraic Discrete Methods 8 (1987), no. 4, 564–577. MR 918059, DOI 10.1137/0608046
P. Assouad and M. Deza, Espaces métriques plongeables dans un hypercube: aspects combinatoires, Ann. Discrete Math. 8 (1980), 197–210 (French). MR 597174

Metric subspaces of

David Avis, Hypermetric spaces and the Hamming cone, Canadian J. Math. 33 (1981), no. 4, 795–802. MR 634138, DOI 10.4153/CJM-1981-061-5

All the facets of the six point Hamming cone

Keith Ball, Isometric embedding in $l_p$-spaces, European J. Combin. 11 (1990), no. 4, 305–311. MR 1067200, DOI 10.1016/S0195-6698(13)80131-X

Remark concerning the euclidean four-point property

7

Theory and applications of distance geometry

P. J. Cameron, J.-M. Goethals, J. J. Seidel, and E. E. Shult, Line graphs, root systems, and elliptic geometry, J. Algebra 43 (1976), no. 1, 305–327. MR 441787, DOI 10.1016/0021-8693(76)90162-9
Dragoš M. Cvetković, Michael Doob, and Horst Sachs, Spectra of graphs, Pure and Applied Mathematics, vol. 87, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], New York-London, 1980. Theory and application. MR 572262
M. E. Tylkin, On Hamming geometry of unitary cubes, Soviet Physics. Dokl. 5 (1960), 940–943. MR 0122636
R. L. Graham, On isometric embeddings of graphs, Progress in graph theory (Waterloo, Ont., 1982) Academic Press, Toronto, ON, 1984, pp. 307–322. MR 776809
John B. Kelly, Hypermetric spaces, The geometry of metric and linear spaces (Proc. Conf., Michigan State Univ., East Lansing, Mich., 1974) Lecture Notes in Math., Vol. 490, Springer, Berlin, 1975, pp. 17–31. MR 0405367
Hiroshi Maehara, Regular embeddings of a graph, Pacific J. Math. 107 (1983), no. 2, 393–402. MR 705757
Hiroshi Maehara, Metric transforms of finite spaces and connected graphs, Discrete Math. 61 (1986), no. 2-3, 235–246. MR 855328, DOI 10.1016/0012-365X(86)90094-4
J. von Neumann and I. J. Schoenberg, Fourier integrals and metric geometry, Trans. Amer. Math. Soc. 50 (1941), 226–251. MR 4644, DOI 10.1090/S0002-9947-1941-0004644-8
R. L. Roth and P. M. Winkler, Collapse of the metric hierarchy for bipartite graphs, European J. Combin. 7 (1986), no. 4, 371–375. MR 868554, DOI 10.1016/S0195-6698(86)80008-7
I. J. Schoenberg, Remarks to Maurice Fréchet’s article “Sur la définition axiomatique d’une classe d’espace distanciés vectoriellement applicable sur l’espace de Hilbert” [MR1503246], Ann. of Math. (2) 36 (1935), no. 3, 724–732. MR 1503248, DOI 10.2307/1968654
I. J. Schoenberg, Metric spaces and completely monotone functions, Ann. of Math. (2) 39 (1938), no. 4, 811–841. MR 1503439, DOI 10.2307/1968466
Lowell W. Beineke and Robin J. Wilson (eds.), Selected topics in graph theory, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], London-New York, 1978. MR 543656
Paul Terwilliger and Michel Deza, The classification of finite connected hypermetric spaces, Graphs Combin. 3 (1987), no. 3, 293–298. MR 903619, DOI 10.1007/BF01788552
W. A. Wilson, On Certain Types of Continuous Transformations of Metric Spaces, Amer. J. Math. 57 (1935), no. 1, 62–68. MR 1507055, DOI 10.2307/2372019
Peter M. Winkler, On graphs which are metric spaces of negative type, Graph theory with applications to algorithms and computer science (Kalamazoo, Mich., 1984) Wiley-Intersci. Publ., Wiley, New York, 1985, pp. 801–810. MR 812709
H. S. Witsenhausen, Minimum dimension embedding of finite metric spaces, J. Combin. Theory Ser. A 42 (1986), no. 2, 184–199. MR 847549, DOI 10.1016/0097-3165(86)90089-0