[math-fun] Embedding simplicial complexes in Euclidean space
Recall what a simplicial complex is: First, an n-simplex delta_n is the convex hull of any n+1 points, in n-space, that lie in no hyperplane. The convex hull of any k+1 of these points is a k-simplex, and is called a k-face of delta_n. The faces of delta_n are all of its k-faces for all k = 0,1,...,n-1. A "simplical complex" is the result of gluing together a disjoint collection of simplices such that if two simplices are glued to each other, they are identified by an affine bijection from a k-face of one to a k-face of another, for some k. Thus in a simplicial complex, any two simplices that intersect do so in solely *one* common face. We shall assume that a simplicial complex K is *connected* -- i.e., for any two simplices s, t of K, there is a sequence of simplices s_0,...,s_L such that s = s_0, s_L = t, and that s_j and s_(j+1) are glued along a (now) common k-face for some k. We also assume a simplicial complex is built from only a *finite* collection of simplices. ---------------------------------------------------------------------------------------------------------- The dimension dim(K) of a simplical complex K is the highest dimension of any simplex of K. QUESTION 1: Is there a least dimension E(n) such that any simplical complex of dimension n can be *topologically* embedded in the Euclidean space of dimension f(n) ? I think this can be done by dipping the complex in goo so that it becomes a subset of a manifold (with boundary) of some dimension d >= n . . . and then use the result that all d-manifolds can be topologically embedded in 2d-dimensional Euclidean space (I think even lower for d-manifolds with nonempty boundary). If a topological embedding of a simplicial complex into Euclidean space is affine on each simplex (and hence must send each simplex to a simplex), we call the embedding *affine*. QUESTION 2: Can every simplicial complex K of dimension n be *affinely* embedded in some Euclidean space? (See Example below.) QUESTION 3: Among those simplicial complexes K (with dim(K) = n) that *do* embed affinely in some Euclidean space, is there a least dimension A(n) such that they can all be affinely embedded in the Euclidean space of dimension A(n) ? Example: Form a strip of three 2-simplices, using equilateral triangles to make an isosceles trapezoid. Identify its left edge with its right edge, abstractly, to form a topological Moebius band. Which can of course be embedded topologically in R^3. But surely this can't be embedded affinely in R^3. It probably can't be embedded affinely in any Euclidean space. (BUT, this is *not* a simplicial complex, since the two outer triangle intersect in both a 1-simplex and a separate 0-simplex.) --Dan
On 11/22/06, Daniel Asimov <dasimov@earthlink.net> wrote:
... QUESTION 1: Is there a least dimension E(n) such that any simplical complex of dimension n can be *topologically* embedded in the Euclidean space of dimension f(n) ?
I think this can be done by dipping the complex in goo so that it becomes a subset of a manifold (with boundary) of some dimension d >= n . . . and then use the result that all d-manifolds can be topologically embedded in 2d-dimensional Euclidean space (I think even lower for d-manifolds with nonempty boundary).
If a topological embedding of a simplicial complex into Euclidean space is affine on each simplex (and hence must send each simplex to a simplex), we call the embedding *affine*.
Outside my purview this one, but surely the above argument must be correct!
QUESTION 2: Can every simplicial complex K of dimension n be *affinely* embedded in some Euclidean space? ...
I'm taking "affinely" to mean isometrically, rather than projectively. [I've never managed to work out what people mean by this word --- I gather it might have something to do with having one foot nailed to the origin ...]
QUESTION 3: Among those simplicial complexes K (with dim(K) = n) that *do* embed affinely in some Euclidean space, is there a least dimension A(n) such that they can all be affinely embedded in the Euclidean space of dimension A(n) ? ... --Dan
Both these questions are addressed by this theorem of distance geometry: A set of k >= m+3 "points", defined only by their distances, is embeddable in m dimensions if and only if either: k > m+3 and all the (m+2)-subsets are so embeddable; or k = m+3 and there exists an (m+3)-simplex with those edge-lengths. However, there exist "pseudo-Euclidean" sets of k = m+3 points with embeddable (m+2)-subsets which are not so embeddable. The construction of counter-examples for m = 2 (5 points in 2-space) depends on the employment of "isogonally conjugate" points in a triangle. When I encountered it some 10 years ago, it appeared at the time so elegantly obvious that I didn't bother to write it down, so now of course I can't recall it. Instead, try consulting the (elusive) book Leonard M. Blumenthal "Distance Geometry ..."; or the original paper (at JSTOR, currently inaccessible to me) Karl Menger "New Foundation of Euclidean Geometry" American Journal of Mathematics Vol. 53 (1931) 721-745]. However, a simpler counterexample suffices to establish a negative response to QUESTION 2. In 2-space for example, consider the boundary K of the (complex) simplex with three equilateral base edges length 9, the other three length 5. Since 9/2 < 5 < 3sqrt3 this does not embed; although all its simplices are embeddable, having dimension at most 2. The construction generalises easily to any dimension, trivially for m = 1. As simplicial complexes these objects are special in that all possible simplices of dimension up to m+1 are incorporated, and those of dimension m+1 have content zero. In particular, there is no possibility of parts of the complex "flapping around" to ease embedding. For such complexes m = n+1, and the answer to QUESTION 3 for k > n+4 is by the theorem A(n) = n-1. I have not looked at strengthening this to n-content nonzero, though I expect that is possible. Cayley-Menger determinants and Distance Geometry had an airing on math-fun in 1997-8, under the subject lines: "Q: embedding graphs in planes and higher dimensions" "Dissection problems" Fred Lunnon
On Thursday 23 November 2006 01:48, Fred lunnon wrote:
QUESTION 2: Can every simplicial complex K of dimension n be *affinely* embedded in some Euclidean space? ...
I'm taking "affinely" to mean isometrically, rather than projectively. [I've never managed to work out what people mean by this word --- I gather it might have something to do with having one foot nailed to the origin ...]
"Affine" just means "linear plus constant", or "f(au+bv) = a.f(u)+b.f(v) when a+b=1". It doesn't imply isometric. This is sufficiently well known that I suspect I'm missing some subtlety; is there, for instance, some reason why Dan's question becomes trivial or stupid if "affine" is given its usual meaning? -- g
participants (3)
-
Daniel Asimov -
Fred lunnon -
Gareth McCaughan