Convexity in finite metric spaces (Q1337115): Difference between revisions

A subset \(S\) of a metric space \((X,d)\) is called \(d\)-convex if for every pair of points \(x, y \in S\) all the points between \(x\) and \(y\) belong to \(S\). Let \({\mathfrak C}_ d\) be the family of all \(d\)-convex subsets of \((X,d)\). Then \((X, {\mathfrak C}_ d)\) is a convexity structure (Prop. 1), i.e., \(\emptyset \in {\mathfrak C}_ d\) and \({\mathfrak C}_ d\) is closed under intersection of any subfamily. The paper concerns two kinds of embeddings: isometric and convex (i.e. convexity preserving) embeddings. In particular, it concerns embeddability of (finite) metric spaces into \(\mathbb{R}^ n\) with either Euclidean metric \(d_ e\) or ``max'' metric \(d_ m\), or into the so called Hamming space \((\{0, 1\}^ n,h)\) with \(h(x,y) = \sum | x_ i - y_ i |\). The paper contains many interesting open problems and a number of results.