If $(X,d)$ is a metric space, we associate with it a simple, undirected graph, called its proximity graph $G(X,d)$ given by $V(G(X,d)) = X$ and $$E(G(X,d)) = \big\{\{x,y\}:x\neq y\in X \text{ and } d(x,y)\leq 1\big\}.$$

As MO user @YCor pointed out in a comment to a recent deleted question, given any (not necessarily finite) simple, undirected graph $G=(V,E)$, the map $d:V\times V\to \mathbb{R}$ given by $d(v,v) = 0$ for $v\in V$, $d(v,w)=1$ iff $\{v,w\}\in E$ and $d(v,w) = 2$ otherwise gives a metric on $V$ such that $G\cong G(V,d)$.

If $G=(V,E)$ is a finite graph we define its spatial dimension $\text{dim}_s(G)$ to be the smallest non-negative integer $n$ such that there is $S\subseteq\mathbb{R}^n$ with $G \cong G(S,||\cdot||)$, where $||\cdot||$ denotes the Euclidean metric that $S$ inherits from $\mathbb{R}^n$.

Question. Given any integer $n\geq 1$, what is an example of a finite graph $G=(V,E)$ with $\text{dim}_s(G)=n$?


If $s$ obeys $k_{n-1}<s$, where $k_n$ is the kissing number of $n$-dimensional Euclidean space, then the star $K_{1,s}$ has dimension at least $n$. For instance, $K_{1,7}$ has dimension 3.

(In most cases where $s\le k_n$, $K_{1,s}$ has dimension exactly $n$, but there are exceptions. For instance $K_{1,6}$ has dimension 3, even though $6\le k_2$, because it turns out not to be possible for six unit disks in the plane to all touch a central disk without touching each other.)

  • $\begingroup$ So is it possible for every $n\in\mathbb{N}$ to find a graph with spatial dimension exactly $n$? (Sorry if I am a bit slow in understanding whether your answer implies this.) $\endgroup$ – Dominic van der Zypen Dec 10 '18 at 13:49
  • $\begingroup$ It seems very likely that this construction (with $s=k_{n-1}+1$) generates a graph with dimension exactly $n$, but it would require a proof that the graph $K_{1,s}$ can actually be embedded without extra ball intersections into $n$-dimensional space. There should be plenty of room to achieve this but I don't see how to prove it in generality. $\endgroup$ – David Eppstein Dec 10 '18 at 19:59

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.