2
$\begingroup$

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$?

$\endgroup$

1 Answer 1

3
$\begingroup$

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.)

$\endgroup$
2
  • $\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$ Dec 10, 2018 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$ Dec 10, 2018 at 19:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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