Hostname: page-component-cd9895bd7-dk4vv Total loading time: 0 Render date: 2024-12-25T05:24:27.087Z Has data issue: false hasContentIssue false
  • English
  • Français

Hypermetric Spaces and the Hamming Cone

Published online by Cambridge University Press:  20 November 2018

David Avis
David Avis*
Affiliation:
McGill University, Montreal, Quebec
Rights & Permissions [Opens in a new window]

Extract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

We denote by d = (d12, …, d1n, d23, …, dn-1,n) a vector of distances between n points. Such a vector d is called a metric if it satisfies the triangle inequalities

(1)

The set of all metrics on n points forms a convex polyhedral cone, the extremal properties of which are discussed in [4]. We will be concerned with a sub-cone that is spanned by metrics of the form

(2)

where t ≧ 0, V is a proper subset of {1, 2, …, n}; and the symbol ⊥ is used for “exclusive or”: i ⊥ j ∈ V means i ∈ V, j ∉ V or i ∉ V,j∉ V.

Type
Research Article
Information
Canadian Journal of Mathematics , Volume 33 , Issue 4 , 01 August 1981 , pp. 795 - 802
Copyright
Copyright © Canadian Mathematical Society 1981

References

1. Assouad, P., Un espace hypermétrique non plongeable dans un espace L\, C. R. Acad. Se. Paris 285 (1977), 361–363.Google Scholar
2. Assouad, P. and Deza, M., Isometric embedding in L\, in hypercubes and related problems, manuscript (1979).Google Scholar
3. Avis, D., On the Hamming cone, Technical report 77-5, Department of Operations Research, Stanford University, Stanford (1977).Google Scholar
4. Avis, D., On the extreme rays of the metric cone, Can. J. Math. 32 (1980), 126–144.Google Scholar
5. Blake, I. and Gilchrist, J., Addresses for graphs, IEEE Trans, on Information Theory 19 (1973), 683–688.Google Scholar
6. Deza, M., Matrices de formes quadratiques non negatives pour des arguments binaries, C. R. Acad. Sc. Paris 277 (1973), 873–875.Google Scholar
7. Deza, M., On Hamming geometry of unitary cubes, (Russian), Doklady Akad. Nuak. SSR 134 (1960), 1037–1040.Google Scholar
8. Deza, M., Linear metric properties of binary codes, (Russian), Proc. 4th Soviet Union Conference on coding theory and transmission information, Moscow-Tashkent (1969), 77–85.Google Scholar
9. Djokovic, D. Z., Distance preserving subgraphs of hypercubes, J. Comb. Th. B 14 (1973), 263–267.Google Scholar
10. Harary, F., Graph theory (Addison-Wesley, Reading, Mass., 1969).Google Scholar
11. Kelly, J. B., Metric inequalities and symmetric differences, in Inequalities II (Academic Press, New York, 1970), 193–212.Google Scholar
12. Kelly, J. B., Hypermetric spaces, in Lecture Notes in Math. 490 (Springer-Verlag, 1975), 17–31.Google Scholar
13. Stoer, J. and Witzgall, C., Convexity and optimization infinite dimensions I (Springer- Verlag, Berlin, 1970).Google Scholar