Beiträge zur Algebra und Geometrie Contributions to Algebra and Geometry Volume 43 (2002), No. 1, 27-31.

Configuration Spaces of Weighted Graphs in High Dimensional Euclidean Spaces

Olivier Mermoud Marcel Steiner

Département de Génie Mécanique, ICAP-LICP, EPFL CH-1015 Lausanne e-mail: olivier.mermoud@epfl.ch

Département de Mathématiques, EPFL CH-1015 Lausanne e-mail: marcel.steiner@epfl.ch

Abstract. Let G = (V, E, d) be any connected weighted graph which admits not only degenerated realisations in the n-dimensional Euclidean space. Its configuration space is always homeomorphic to a (\frac{1}{2}n(n + 1) − e)-dimensional sphere, where n is the number of vertices minus one and e the number of edges.

1. Introduction and results

We consider point sets in fixed high dimensional Euclidean space with given distances between certain pairs of points, called weighted graphs. The configuration space of a weighted graph is the set of all possible realisations modulo the group of proper isometries of the Euclidean space (with the natural topology).

Recently several authors showed a universality theorem for weighted graphs in the plane, [2], [3] and [5]: for any compact real algebraic variety there exists a weighted graph in the plane such that its configuration space contains this variety as a component. The situation changes radically if we consider weighted graphs which admit not only degenerated realisations in high dimensional Euclidean space. If the Euclidean space has dimension at least the number of vertices, then the configuration space is always a closed ball, and if the dimension is equal to the number of vertices minus one, then the configuration space is always a sphere. It is surprising that the dimension of the ball, respectively the sphere does not depend on the weights but only on the number of edges:

0138-4821/93 $ 2.50 \begin{matrix}c \\ ◯ \end{matrix} 2002 Heldermann Verlag

28 O. Mermoud, M. Steiner: Configuration Spaces of Weighted Graphs …

Theorem. Let G = (V, E, d) be a connected weighted graph with n = #V − 1 and e = #E which admits not only degenerated realisations in the Euclidean space ℝ^{n}. The configuration space [G]_{n}^{+} of G is homeomorphic to the sphere S^{\frac{1}{2} n(n+1)−e}.

Of special interest is the case of weighted graphs with m ≥ 3 vertices which are joined in cyclic order by edges of positive weights in the (m − 1)-dimensional Euclidean space:

Corollary. Let P_{m} be an m-gon which admits not only an aligned realisation in the Euclidean space ℝ^{m−1}. The configuration space [P_{m}]_{m−1}^{+} of P_{m} is homeomorphic to the sphere S^{\frac{1}{2} m(m−3)}.

It is a well known fact, that the configuration space of any quadrilateral in three-space is homeomorphic to a two-dimensional sphere. This is a special case of the above corollary.

2. Definitions and proofs

Let us start with the definition of the main objects with which we deal:

Definition. The triple G = (V, E, d) consisting of

(1) a set of vertices V = {V_{0}, V_{1}, …, V_{n}},

(2) a set of edges E = {{V_{i_{1}}, V_{j_{1}}}, …, {V_{i_{e}}, V_{j_{e}}}} with i_{l}, j_{l} ∈ {0, 1, …, n}, i_{l} ≠ j_{l} and (3) a weight function d : E → ℝ_{+}, that attaches to every edge {V_{i_{l}}, V_{j_{l}}} in E a positive

weight d(V_{i_{l}}, V_{j_{l}}) ∈ ℝ_{+}, is called a weighted graph.

If a weighted graph contains several components, each of them can be treated separately and the total non-compact configuration space can be assembled. Therefore only connected weighted graphs are interesting, i.e. graphs in which any two vertices are connected by a sequence of edges.

An m-gon P_{m} is a special connected weighted graph given by m vertices which are joined in cyclic order by m edges of positive weights.

We call a connected weighted graph G = (V, E, d) realisable in ℝ^{r}, if there exists Φ : V → ℝ^{r} such that

|Φ(V_{i}) − Φ(V_{j})| = d(V_{i}, V_{j}) for all {V_{i}, V_{j}} in E.

A realisation ξ of G = (V, E, d) in ℝ^{r} is an (n + 1)-tuple of points (p_{0}, p_{1}, …, p_{n}) ⊂ (ℝ^{r})^{n+1} such that |p_{i} −p_{j}| = d(V_{i}, V_{j}) if {V_{i}, V_{j}} is an element of E. A realisation ξ of G in ℝ^{r} is called degenerated if ξ is also a realisation in ℝ^{r−1}. For polygons in the plane degenerate realisations correspond exactly with critical values of the Morse function defining the configuration space, cf. [1] and [4]. The configuration space of G in ℝ^{r} is

[G]_{r}^{+} = {ξ realisation of G in ℝ^{r}}/Iso^{+}(ℝ^{r})

with the natural topology. Iso^{+}(ℝ^{r}) is the group of orientation preserving isometries of ℝ^{r}. We also make use of [G]_{r} = {ξ realisation of G in ℝ^{r}}/Iso(ℝ^{r}), the space of all realisations modulo the group of isometries of ℝ^{r}. The natural involution τ on O(r) induces an involution τ̃ on [G]_{r}^{+}, hence

[G]_{r} = [G]_{r}^{+} /τ̃.  (1)

Set k = \binom{#V}{2} − #E = \frac{1}{2}n(n + 1) − e, the number of edges which have no prescribed weight. Let ξ be a realisation of G = (V, E, d) in ℝ^{r}. For all l ∈ {0, 1, …, k − 1} set x_{l} := |p_{i_{l}} − p_{j_{l}}| if {V_{i}, V_{j}} is not an element of E. The k parameters x_{0}, x_{1}, …, x_{k−1} are the length of the distances between vertices, which are not prescribed. They can be used as a natural parametrisation of the configuration space.

Further let us define for any integer r ≥ 1 the subset

Ω_{r}(G) = \{x ∈ ℝ^{k} | \begin{matrix}∃ ξ non-degenerated realisation of G in ℝ^{r} \\ with |p_{i_{l}} − p_{j_{l}}| = x_{l}, ∀ l ∈ \{0, 1, …, k − 1\} \end{matrix} \}

of ℝ^{k}. Notice that if n = #V − 1 and if G admits not only degenerated realisations in ℝ^{n} then Ω_{n}(G) is homeomorphic to [G]_{n}. Moreover if N ≥ #V then Ω_{N}(G) is empty.

After these preliminaries we give the proof of the theorem. Our aim consists in showing, that [G]_{n} is homeomorphic to a k-dimensional ball, where k = \frac{1}{2}n(n + 1) − e. Using (1) the configuration space [G]_{n}^{+} can be obtained as follows: take two copies of [G]_{n} and attach their boundaries. This results in a (\frac{1}{2}n(n + 1) − e)-dimensional sphere. Thus we have to show the following two lemmas. The first lemma, due to Schoenberg [6], is a criterion for the distance preserving embedding of a complete weighted graph in an r-dimensional Euclidean space:

Lemma 1. Let G = (V, E, d) be a connected weighted graph with E = {{V_{i}, V_{j}} | 0 ≤ i < j ≤ n}, i.e. every vertex in V is joined with all others by an edge {V_{i}, V_{j}} of prescribed length d_{ij} = d(V_{i}, V_{j}). Further let r be an integer with 1 ≤ r ≤ n = #V − 1. There exists a non-degenerated realisation of G in ℝ^{r} if and only if the quadratic form Q : ℝ^{n} → ℝ given by

Q(v) = \frac{1}{2} ∑_{i,j=1}^{n}(d_{0i}^{2} + d_{0j}^{2} − d_{ij}^{2})v_{i}v_{j}

is positive and has rank r.

Proof. Let ξ be a non-degenerated realisation of G given by the tuple (p_{0}, p_{1}, …, p_{n}) of n + 1 points in ℝ^{n} with |p_{i} − p_{j}| = d(V_{i}, V_{j}) = d_{ij} for all i, j ∈ {0, 1, …, n} with i ≠ j. Consider v = ∑_{i=1}^{n} v_{i}(p_{i} − p_{0}) with v_{i} ∈ ℝ and notice that

Q(v) = ⟨v, v⟩ = ∑_{i,j=1}^{n}⟨p_{i} − p_{0}, p_{j} − p_{0}⟩v_{i}v_{j}

= ∑_{i,j=1}^{n} d_{0i}d_{0j} cos(∡(p_{i} − p_{0}, p_{j} − p_{0}))v_{i}v_{j}

= \frac{1}{2} ∑_{i,j=1}^{n}(d_{0i}^{2} + d_{0j}^{2} − d_{ij}^{2})v_{i}v_{j}.

Since the vectors p_{1} − p_{0}, …, p_{n} − p_{0} span an r-dimensional vector space the quadratic form Q has rank r. Further if x ≠ 0 then Q(x) = |x|^{2} > 0, so Q is positive.

The quadratic form Q is positive and has rank r. A transformation S ∈ GL(n, ℝ) exists, such that Q = S^{t} I_{r} S, where I_{r} = diag(1, …, 1, 0, …, 0) with rank r. Let e_{1}, …, e_{n} be the standard basis of ℝ^{n} and set p_{0} = 0 and p_{i} = I_{r} S e_{i}, then

|p_{i}|^{2} = |I_{r} S e_{i}|^{2} = ⟨S^{t} I_{r}^{t} I_{r} S e_{i}, e_{i}⟩ = ⟨S^{t} I_{r} S e_{i}, e_{i}⟩ = Q(e_{i}) = d_{0i}^{2}

for all i ∈ {1, …, n} and by linearity |p_{i} − p_{j}|^{2} = Q(e_{i} − e_{j}) = d_{ij}^{2} for all i, j ∈ {1, …, n} with i ≠ j. In other words the (n + 1)-tuple (p_{0}, p_{1}, … p_{n}) is a realisation of G in ℝ^{r} × {0} ⊂ ℝ^{n}.

If G were realisable in ℝ^{r−1} then by the first half the quadratic form Q had rank r − 1, which contradicts the assumption.

Lemma 2. Let G = (V, E, d) be a connected weighted graph with #V = n + 1 which admits not only degenerated realisations in ℝ^{n}. Then Ω_{n}(G) is a bounded and simply connected subset of ℝ^{k}. If further ∂ Ω_{n}(G) signifies the boundary of Ω_{n}(G), then

∂Ω_{n}(G) = ⋃_{m<n} Ω_{m}(G).

Proof. Consider the map F : ℝ^{k} × ℝ^{n} → ℝ defined by

F (x, v) = Q_{x}(v) = ∑_{i,j=1}^{n} (f_{0i}(x) + f_{0j}(x) − f_{ij}(x)) v_{i}v_{j},

where

f_{ij}(x) = \{ \begin{matrix}d(V_{i}, V_{j})^{2} & if & \{V_{i}, V_{j}\} ∈ E \\ x_{l} & if & \{V_{i_{l}}, V_{j_{l}}\} ∉ E \end{matrix}

Lemma 1 implies that the graph G has a non-degenerated realisation (p_{0}, p_{1}, …, p_{n}) in ℝ^{n}, with |p_{i_{l}} −p_{j_{l}}| = x_{l} for all {i_{l}, j_{l}} such that {V_{i_{l}}, V_{j_{l}}} ∉ E, if and only if the quadratic form Q_{x} is positive and has rank n. Notice that by bi-linearity, it is sufficient to test Q_{x} for positivity only on S^{n−1} ⊂ ℝ^{n}. This fact allows us to define φ : ℝ^{k} → ℝ by φ(x) = min_{v∈S^{n−1}} F (x, v). We then have

Ω_{n}(G) = {x ∈ ℝ^{k} | φ(x) > 0}.

The mapping x ↦ F (x, v) being affine, φ is the minimum of a family of affine functions. This implies that φ is concave, i.e. if x, y ∈ ℝ^{k} then

φ(λx + (1 − λ)y) ≥ λφ(x) + (1 − λ)φ(y) for all λ ∈ [0, 1].

As the function φ is concave, the subset Ω_{n}(G) is a simply connected subset of ℝ^{k}. Since G is connected Ω_{n}(G) is bounded.

Finally, Lemma 1 implies that the set of degenerate realisations of G in ℝ^{n} is given by

⋃_{m<n} Ω_{m}(G) = {x ∈ ℝ^{k} | φ(x) = 0} = ∂ Ω_{n}(G).

Notice that φ(x) < 0 if x ∉ (ℝ_{+})^{k}. If G is not realisable then Ω_{n}(G) is empty by Lemma 1.

The dimension of the affine hull of the vertices is at most n = #V − 1, therefore Ω_{n}(G) is homeomorphic to [G]_{#V +N} for all N ∈ ℕ. The configuration space of weighted graphs in ℝ^{#V +N} for any N ∈ ℕ is therefore stable, in other words [G]_{#V +N} is an (\frac{1}{2}n(n + 1) − e)- dimensional ball.

References

[1] Hausmann, J.-C.: Sur la topologie des bras articulés. Lecture Notes in Math. 1474 (1989), 146–159. Zbl 0736.57014

[2] Jordan, D.; Steiner, M.: Configuration Spaces of Mechanical Linkages. Discrete Comput. Geom. 22 (1999), 297–315. Zbl 0990.69556

[3] Jordan, D.; Steiner, M.: Compact Surfaces as Configuration Spaces of Mechanical Linkages. To appear in: Israel J. Math.

[4] Kapovich, M.; Millson, J.: On the Moduli Space of Polygons in the Euclidean Plane. J. Differential Geom. 42 (1995), 133–164. Zbl 0847.51026

[5] Kapovich, M.; Millson, J.: Universality Theorems for Configuration Spaces of Planar Linkages. To appear in: Topology.

[6] Schoenberg, I. J.: Remarks to Maurice Fréchet’s Article “Sur la définition axiomatique d’une classe d’espaces distancés vectoriellement applicable sur l’espace de Hilbert”. Ann. of Math. 36 (1935), 724–732. Zbl 0012.30703

Received April 29, 2000