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?

  • 2
    $\begingroup$ 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. $\endgroup$ – Florian Lehner Oct 17 '18 at 13:56
  • $\begingroup$ @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. $\endgroup$ – Dominic van der Zypen Oct 18 '18 at 6:50
  • $\begingroup$ I just posted my comment as an answer. $\endgroup$ – Florian Lehner Oct 18 '18 at 15:23

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.