Embedding a weighted graph into $\mathbb{R}^n$

335 Views Asked by At

Given a weighted graph $G$, what is the least dimension $n$ for which there exists an embedding $f:V(G)\hookrightarrow\mathbb{R}^n$ such that the the weight of an edge $(v_1,v_2)$ is the distance $||f(v_2)-f(v_1)||$ in $\mathbb{R}^n$? One immediate restriction is that the weights on $G$ all satisfy the triangle inequality: the sum of the weights of the edges $(v_1,v_2)$ and $(v_2,v_3)$ is less than or equal to the weight of $(v_1,v_3)$.

Consider the complete graph on 4 vertices $K_4$ with a uniform weight of $1$. To embed $K_4$ into $\mathbb{R^n}$ requires $n\geq 3$ and yields the beloved tetrahedron. Notice that if a graph can be embedded into $\mathbb{R}^n$, there is a natural embedding into $\mathbb{R}^{n+1}$ via $G\mapsto f(G)\times\{0\}$ where $\times$ denotes the Cartesian product. $K_3$ requires $n\geq 2$, and $K_2$ can be embedded into $\mathbb{R}$ itself: take $f(V)=\{0,1\}$.

Proposition 1. Let $K_n$ be the complete graph on $n$ vertices with a uniform weight of $1$. Call an embedding $f:V(G)\hookrightarrow\mathbb{R}^n$ a weighted embedding if $$\forall(v_1,v_2)\in E(G),\quad||f(v_2)-f(v_1)||=w(v_1,v_2)$$ Then any weighted embedding $f:V(K_n)\hookrightarrow\mathbb{R}^m$ has $m\geq n-1$.

Proof: The cases $n\leq 4$ should be easy enough to visualize in $\mathbb{R}^n$ (the point, a line segment, a triangle, and a tetrahedron). The comments provide a hypergeometric selection argument: Given the position $f(v_1)\in\mathbb{R}^n$, the possible values of $f(v_2)$ lie in the unit hyperball of dimension $n$ centered at $f(v_1)$. Once $f(v_2)$ is selected, the solutions for $f(v_3)$ lie in the intersection of two $n$-balls, yielding a $(n-1)$-ball. In general, once we select $f(v_i)$ for $i<n$, the solution set for $f(v_n)$ is a unit hyperball of dimension $(n-i)$. The solution set for $f(v_{n-1})$ is the $0$-ball, or a pair of points. Setting $f(v_{n-1})$ to either of these points is a valid solution. The solution set for $f(v_n)$ is the empty set. Thus, $\mathbb{R}^n$ can contain the complete graph of at most $n-1$ vertices.