What is the minimum embedding dimension for a given graph with unit line-segments as edges?

143 Views Asked by At

For a given finite set of edges $E$, what is the minimum value of $n\in\mathbb{Z}_{>0}$ such that $\mathbb{R}^n$, such that the given graph can be constructed with each edge between two vertices being a unit line-segment?

Note: Edges are allowed to intersect other edges and vertices. But no two vertices may occupy the same point.

E.g; if $E=\{\{a,b\},\{b,c\},\{c,a\}\}$, then $E$, forms an equilateral triangle $\triangle abc$, which must be embedded with these conditions in minimum $\mathbb{R}^2$.

As another example, the edges of a unit-simplex can be embedded with these conditions in at minimum $\mathbb{R}^4$.

Beyond trivial maximum bounds like $n<|E|$, and $n<k$ for $k$ vertices, I'm unsure on how to continue.

I suppose what I'm asking if there exists some function $f(E)=n$. Also, let me know if my terminology/notation for this problem can be improved.

1

There are 1 best solutions below

2
On

Not an answer, but too long for comments

I think that the question might be this:

You're given a set $$ of distinct pairs $(, )$, with $1 \le i, j \le n$, and with all the numbers $1,\ldots, n$ appearing in either the first or second entry of some item in $E$. [This condition means you can't be given $(4, 5)$, $(5, 6)$, $(6, 4)$, or at least that if you ARE given that, you should rewrite it as $(1,2), (2, 3), (3, 1)$.]

Let $v_i$ denote $(0, \ldots, \frac{1}{\sqrt{2}}, \ldots, 0$, where the nonzero entry is at location $i$.

Construct a collection $G(E)$ of line segments in $\Bbb R^n$ associated to $E$ by including in $G$ the unit-length segment from $v_i$ to $v_j$ if and only if $(i,j) \in E$.

A function $f$ sending each point $v_i$ to a point $p_i = f(v_i) \in \Bbb R^k$ can be extended, piecewise linearly, to a function $\bar{f}$ on $G(E)$. The image $\bar{f}(G(E))$ looks like a "connect-the-dots" version of $G(E)$ in $R^k$. If $f$ has the property that $d(p_i, p_j) = 1$ whenever $(i,j) \in E$, we can say that $f$ "preserves lengths".

Equivalently, and perhaps more simply (avoiding the explicit construction of the set $G(E)$ which "looks" like the graph defined by $E$, we can say this.

Again, given $E$ as above, a map $f:\{1, \ldots n\} \to \Bbb R^k$ is "nice for $E$" if

  1. it's injective, and

  2. for all $(i, j) \in E$, we have $d(f(i), f(j)) = 1$.

The idea here is that letting $P_i = f(i)$, and drawing in the straight-line segments from $P_i$ to $P_j$, for every $(i,j) \in E$, we get the kind of picture that OP was thinking of.

The question is then, "Given $E$, what's the smallest dimension $k$ such that there's a map $f: \{1, \ldots, n\} \to \Bbb R^k$ that's nice for $E$?"

I still worry, however, that the OP really probably wants to restrict to maps for which the edges of $E$ meet only transversely. In particular, the two adjacent squares at the top of the following diagram define a set of unit-length edges $E$. The second drawing, below, shows a positioning of the 6 dots in a way that's "nice for $E$", but may not be what OP is looking for, because two of the vertical edges of the shape "overlap a lot", even though all six vertices are distinct. enter image description here

Either way (whether this last example is good or not), I think that perhaps what OP needs to search for is something like "graphs and rigidity", but I could be misremembering what it's actually called.