# Graphs represented by a subset of a metric space

Let $$(X,d)$$ be a metric space, and suppose $$S\subseteq X$$ is a finite subset in which all pairwise distances are distinct (formal definition here).

If $$x\in S$$ and $$k$$ is a non-negative integer with $$k<|S|$$, we define $$S_k(x)\subseteq S$$ to be the set of the $$k$$ nearest members of $$S$$ to $$x$$, other than $$x$$ itself. We define a graph $$G(k,S)$$ by setting $$V(G(k,S)) = S$$, and $$E(G(k,S)) = \big\{\{x,y\}: x\neq y \in S \text{ and } y\in S_k(x) \text{ and }x\in S_k(y)\big\}.$$ So the points $$x,y$$ are connected by an edg if and only if $$y$$ belongs to the $$k$$ nearest points of $$x$$, and vice versa.

We say that a metric space $$(X,d)$$ is graph-universal if for every finite graph $$G$$ there is $$S\subseteq X$$ with pairwise distinct distances, and a non-negative integer $$k<|S|$$ such that $$G\cong G(k,S)$$. For example, $$\mathbb{R}$$ with the Euclidean distance is not graph-universal as we cannot find a set $$S$$ of $$4$$ real points and $$k<4$$ such that $$C_4 \cong G(k, S)$$.

Question. If $$\{0,1\}^{<\omega}$$ denotes the set of functions $$f:\omega\to\{0,1\}$$ that are eventually $$0$$, and endow it with the Hamming distance $$d_H$$, is $$(\{0,1\}^{<\omega}, d_H)$$ graph-universal?

• How would you represent a star in any metric space? The center has $n-1$ neighbours, so we'd have $k = n-1$. But, unless I'm missing something, $G(n-1,S)$ for $|S| = n$ always gives a complete graph. – Florian Lehner Oct 17 '18 at 13:56
• @FlorianLehner that's correct, thanks for this observation! I will delete the question - unless you want to post your argument as an answer -- you are very welcome to! I'll accept and upvote it. – Dominic van der Zypen Oct 18 '18 at 6:50
• I just posted my comment as an answer. – Florian Lehner Oct 18 '18 at 15:23

## 1 Answer

It is not possible to embed any non-complete graph with a universal vertex into any metric space in this way.

A universal vertex in an $$n$$-vertex graph has degree $$n-1$$ and thus $$k = n-1$$ in any representation of such a graph. But if $$|S| = n$$ and $$k = n-1$$, then $$G(k,S)$$ is a complete graph on $$n$$ vertices.