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$ Commented 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$ Commented Dec 10, 2018 at 19:59

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .