Metric transforms and euclidean embeddings. (English) Zbl 0685.51010
The authors’ summary: “It is proved that if \(0\leq c\leq 0,72/n\) then for any n-point metric space (X,d), the metric space \((X,d^ c)\) is isometrically embeddable into an Euclidean space. For 6-point metric space, \(c= \log_ 2 (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”.”
Reviewer: K.Burian
MSC:
| 51K05 | General theory of distance geometry |
| 51M05 | Euclidean geometries (general) and generalizations |
| 05C10 | Planar graphs; geometric and topological aspects of graph theory |
References:
| [1] | 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. · Zbl 0639.51018 · doi:10.1137/0608046 |
| [2] | P. Assouad and M. Deza, Espaces métriques plongeables dans un hypercube: aspects combinatoires, Ann. Discrete Math. 8 (1980), 197 – 210 (French). Combinatorics 79 (Proc. Colloq., Univ. Montréal, Montreal, Que., 1979), Part I. · Zbl 0464.05029 |
| [3] | -, Metric subspaces of \( {L^1}\), Publications Mathematiques d’Orsay, 82. 03, Universite de Paris-Sud, 1982. |
| [4] | David Avis, Hypermetric spaces and the Hamming cone, Canad. J. Math. 33 (1981), no. 4, 795 – 802. · Zbl 0445.52008 · doi:10.4153/CJM-1981-061-5 |
| [5] | -, All the facets of the six point Hamming cone, Technical Report No. SOCS-88.7 1988. |
| [6] | Keith Ball, Isometric embedding in \?_{\?}-spaces, European J. Combin. 11 (1990), no. 4, 305 – 311. · Zbl 0712.46008 · doi:10.1016/S0195-6698(13)80131-X |
| [7] | L. M. Blumenthal, Remark concerning the euclidean four-point property, Ergebnisse eines Math. Koll. 7 (1936), 8-10. |
| [8] | -, Theory and applications of distance geometry, Chelsea, New York, 1970. |
| [9] | 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. · Zbl 0337.05142 · doi:10.1016/0021-8693(76)90162-9 |
| [10] | 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. · Zbl 0824.05046 |
| [11] | M. E. Tylkin, On Hamming geometry of unitary cubes, Soviet Physics. Dokl. 5 (1960), 940 – 943. |
| [12] | R. L. Graham, On isometric embeddings of graphs, Progress in graph theory (Waterloo, Ont., 1982) Academic Press, Toronto, ON, 1984, pp. 307 – 322. R. L. Graham and P. M. Winkler, On isometric embeddings of graphs, Trans. Amer. Math. Soc. 288 (1985), no. 2, 527 – 536. · Zbl 0576.05017 |
| [13] | John B. Kelly, Hypermetric spaces, The geometry of metric and linear spaces (Proc. Conf., Michigan State Univ., East Lansing, Mich., 1974) Springer, Berlin, 1975, pp. 17 – 31. Lecture Notes in Math., Vol. 490. |
| [14] | Hiroshi Maehara, Regular embeddings of a graph, Pacific J. Math. 107 (1983), no. 2, 393 – 402. · Zbl 0477.51019 |
| [15] | Hiroshi Maehara, Metric transforms of finite spaces and connected graphs, Discrete Math. 61 (1986), no. 2-3, 235 – 246. · Zbl 0592.05058 · doi:10.1016/0012-365X(86)90094-4 |
| [16] | J. von Neumann and I. J. Schoenberg, Fourier integrals and metric geometry, Trans. Amer. Math. Soc. 50 (1941), 226 – 251. · Zbl 0028.41002 |
| [17] | R. L. Roth and P. M. Winkler, Collapse of the metric hierarchy for bipartite graphs, European J. Combin. 7 (1986), no. 4, 371 – 375. · Zbl 0619.05042 · doi:10.1016/S0195-6698(86)80008-7 |
| [18] | 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. · Zbl 0012.30703 · doi:10.2307/1968654 |
| [19] | I. J. Schoenberg, Metric spaces and completely monotone functions, Ann. of Math. (2) 39 (1938), no. 4, 811 – 841. · JFM 64.0617.03 · doi:10.2307/1968466 |
| [20] | Lowell W. Beineke and Robin J. Wilson , Selected topics in graph theory, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], London-New York, 1978. · Zbl 0423.00003 |
| [21] | Paul Terwilliger and Michel Deza, The classification of finite connected hypermetric spaces, Graphs Combin. 3 (1987), no. 3, 293 – 298. · Zbl 0618.05043 · doi:10.1007/BF01788552 |
| [22] | W. A. Wilson, On Certain Types of Continuous Transformations of Metric Spaces, Amer. J. Math. 57 (1935), no. 1, 62 – 68. · Zbl 0010.37802 · doi:10.2307/2372019 |
| [23] | 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. |
| [24] | H. S. Witsenhausen, Minimum dimension embedding of finite metric spaces, J. Combin. Theory Ser. A 42 (1986), no. 2, 184 – 199. · Zbl 0594.05024 · doi:10.1016/0097-3165(86)90089-0 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
