Realizing prespecified minimum and maximum distances in metric spaces

Abstract

Given functions f, g : [n] → [n], do there exist n points A1, A2, . . . , An in some metric space such that Af (i), Ag(i) are the points closest and farthest from point Ai? In this paper we characterize precisely which pairs of functions have this property. Define m(k) to be the maximum integer such that any pair of functions f, g : [m(k)] → [m(k)] realizable in some metric space is also realizable in Rk. We show that m(k) grows exponentially in k. This answers a question of Croft. We also discuss what happens when looking at minimum and maximum distances separately.