Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

 
 

 

Metric transforms and Euclidean embeddings


Authors: M. Deza and H. Maehara
Journal: Trans. Amer. Math. Soc. 317 (1990), 661-671
MSC: Primary 51K05
DOI: https://doi.org/10.1090/S0002-9947-1990-0974513-6
MathSciNet review: 974513
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] M. Aschbacher, P. Bald, E. B. Baum and R. M. Wilson, Embedding of ultrametric spaces in finite dimensional structures, SIAM J. Algebraic Discrete Methods 8 (1987), 564-577. MR 918059 (89d:54020)
  • [2] P. Assouad and M. Deza, Espaces metriques plongeables dans un hypercube, Ann. Discrete Math. 8 (1980), 197-210. MR 597174 (82h:05042)
  • [3] -, Metric subspaces of $ {L^1}$, Publications Mathematiques d'Orsay, 82. 03, Universite de Paris-Sud, 1982.
  • [4] D. Avis, Hypermetric space and Hamming cone, Canad. J. Math. 33 (1981), 795-802. MR 634138 (84d:52007)
  • [5] -, All the facets of the six point Hamming cone, Technical Report No. SOCS-88.7 1988.
  • [6] K. Ball, Isometric embedding in $ {l_p}$-spaces, European J. Combin. (to appear). MR 1067200 (92f:52014)
  • [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 goemetry, J. Algebra 43 (1976), 305-327. MR 0441787 (56:182)
  • [10] D. Cvetkovic, M. Doob and H. Sachs, Spectra of graphs, Academic Press, New York, 1980. MR 572262 (81i:05054)
  • [11] M. Deza (as M. E. Tylkin), On Hamming geometry of unitary cubes, Dokl. Akad. Nauk SSR 134 (1960), 1037-1040. MR 0122636 (22:13359)
  • [12] R. L. Graham and P. M. Winkler, On isometric embeddings of graphs, Trans. Amer. Math. Soc. 288 (1985), 527-536. MR 776391 (86f:05055b)
  • [13] J. B. Kelly, Hypermetric spaces, Lecture Notes in Math., Vol. 490, Springer-Verlag 1975, pp. 17-31. MR 0405367 (53:9161)
  • [14] H. Maehara, Regular embeddings of a graph, Pacific J. Math. 107 (1983), 393-402. MR 705757 (84i:05047)
  • [15] -, Metric transforms of finite spaces and connected graphs, Discrete Math. 61 (1986), 235-246. MR 855328 (87m:05085)
  • [16] J. von Neumann and I. J. Schoenberg, Fourier integrals and metric geometry, Trans. Amer. Math. Soc. 50 (1941), 226-251. MR 0004644 (3:37g)
  • [17] R. P. Roth and P. M. Winkler, Collapse of the metric hierarchy for bipartite graphs, European J. Combin. 7 (1986), 371-375. MR 868554 (87k:05075)
  • [18] I. J. Schoenberg, Remarks to Maurice Frechet's article, Ann. of Math. (2) 36 (1935), 724-732. MR 1503248
  • [19] -, Metric space and completely monotone functions, Ann. of Math. (2) 39 (1938), 811-841. MR 1503439
  • [20] A. J. Schewenk and R. J. Wilson, On the eigenvalue of a graph, Selected Topics in Graph Theory (L. W. Beineke and R. J. Wilson, eds.), Academic Press, New York, 1978. MR 543656 (81e:05059)
  • [21] P. Terwillinger and M. Deza, The classification of finite connected hypermetric spaces, Graphs and Combinatorics 3 (1987), 293-298. MR 903619 (88i:05074)
  • [22] W. A. Wilson, On certain types of continuous transformations of metric spaces, Amer. J. Math. 57 (1935), 62-68. MR 1507055
  • [23] P. M. Winkler, On graphs which are metric spaces of negative type, Graph Theory with Application to Algorithms and Computer Science (Y. Alavi et. al., eds.), Wiley, New York, 1985, pp. 801-810. MR 812709 (87b:05054)
  • [24] H. S. Witsenhausen, Minimum dimension embedding of finite metric spaces, J. Combin. Theory Ser. A 42 (1986), 184-199. MR 847549 (88f:54058)

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC: 51K05

Retrieve articles in all journals with MSC: 51K05


Additional Information

DOI: https://doi.org/10.1090/S0002-9947-1990-0974513-6
Article copyright: © Copyright 1990 American Mathematical Society

American Mathematical Society