Minimal and Maximal Distances in Metric Spaces

Abstract

Given functions $f,g:[n]\to [n]$ do there exist $n$ points $A_1,A_2\dots A_n$ in some metric space such that $A_{f(i)},A_{g(i)}$ are the points closest and farthest from point $A_i$? In this paper we characterize precisely which pairs of functions have this property. If the metric space is ${\mathbb{R}}^k$ we show that the maximal number $m(k)$ so that any pair of functions $f,g:[m(k)]\to [m(k)]$ realizable in some metric space is also realizable in ${\mathbb{R}}^k$ grows exponentially in $k$. In the final section of this paper we consider what happens when we look at minimal and maximal distances separately. We show that any function $g$ that can be a maximal distance function can also be a maximal distance function in ${\mathbb{R}}^2$. We also find an interesting family of functions that can be minimal distance functions but not in ${\mathbb{R}}^k$.

22 pages