RE: [math-fun] Embedding simplicial complexes in Euclidean space
Andy wrote: << More simply, take two equilateral triangles, identify all three corners of one with all three corners of the other. This does not have an affine embedding in R^n for all n. This (along with identifying some of the edges of the triangles) is exactly what you've done with the two center triangles of your strip, in your more complex example. Even simpler, in one dimension less, take two line segments, and identify their endpoints. This does not embed in R^n affinely for any n. . . .
The problem is, in a simplicial complex any two simplices that intersect must do so in one common face (of any dimension). So two 2-simplices that intersect in all three 0-faces doesn't qualify. Ditto, of course, for two 1-simplices that intersect in both their endpoints. --Dan
Any finite *simplicial* complex with n vertices is a subcomplex of the (n-1)-simplex, since each simplex in the complex is determied by its set of vertices. Therefore it embeds affinely in R^(n-1). It seems that by a general position argument you can embed a k- dimensional complex affinely in (2k+1)-space. You just need to make sure that a bunch of linear subspaces don't have On Nov 23, 2006, at 4:53 AM, Daniel Asimov wrote:
Make a band of four equilateral triangles in the plane, forming a parallelogram.
Now identify the left and right edges of the parallelogram, creating a simplicial complex K, containing four 2-simplices, that's topologcially a Moebius band.
For all n, there is no topological embedding h: K -> R^n such that h is affine on simplices.
This is not a simplicial complex, because any middle vertex along an edge is connected twice to one of the identified vertices --- once horizontally, and once kitty-cornered (diagonally). Similar mistake to the version below. This illustrates why simplicial complexes are not the most graphically intuitive concept. Bill On Nov 23, 2006, at 12:42 PM, Daniel Asimov wrote:
Andy wrote:
<< More simply, take two equilateral triangles, identify all three corners of one with all three corners of the other. This does not have an affine embedding in R^n for all n. This (along with identifying some of the edges of the triangles) is exactly what you've done with the two center triangles of your strip, in your more complex example.
Even simpler, in one dimension less, take two line segments, and identify their endpoints. This does not embed in R^n affinely for any n.
. . .
The problem is, in a simplicial complex any two simplices that intersect must do so in one common face (of any dimension). So two 2-simplices that intersect in all three 0-faces doesn't qualify.
Ditto, of course, for two 1-simplices that intersect in both their endpoints.
--Dan
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
I should have added that if you have a countable d-dimensional simplicial complex, then a random map of the vertices into R^(2d+1) extends to an affine embedding. Bill On Nov 24, 2006, at 12:52 AM, Bill Thurston wrote:
Any finite *simplicial* complex with n vertices is a subcomplex of the (n-1)-simplex, since each simplex in the complex is determied by its set of vertices. Therefore it embeds affinely in R^(n-1).
It seems that by a general position argument you can embed a k- dimensional complex affinely in (2k+1)-space. You just need to make sure that a bunch of linear subspaces don't have
On Nov 23, 2006, at 4:53 AM, Daniel Asimov wrote:
Make a band of four equilateral triangles in the plane, forming a parallelogram.
Now identify the left and right edges of the parallelogram, creating a simplicial complex K, containing four 2-simplices, that's topologcially a Moebius band.
For all n, there is no topological embedding h: K -> R^n such that h is affine on simplices.
This is not a simplicial complex, because any middle vertex along an edge is connected twice to one of the identified vertices --- once horizontally, and once kitty-cornered (diagonally). Similar mistake to the version below. This illustrates why simplicial complexes are not the most graphically intuitive concept. Bill On Nov 23, 2006, at 12:42 PM, Daniel Asimov wrote:
Andy wrote:
<< More simply, take two equilateral triangles, identify all three corners of one with all three corners of the other. This does not have an affine embedding in R^n for all n. This (along with identifying some of the edges of the triangles) is exactly what you've done with the two center triangles of your strip, in your more complex example.
Even simpler, in one dimension less, take two line segments, and identify their endpoints. This does not embed in R^n affinely for any n.
. . .
The problem is, in a simplicial complex any two simplices that intersect must do so in one common face (of any dimension). So two 2-simplices that intersect in all three 0-faces doesn't qualify.
Ditto, of course, for two 1-simplices that intersect in both their endpoints.
--Dan
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
On 11/24/06, Bill Thurston <wpt4@cornell.edu> wrote:
Any finite *simplicial* complex with n vertices is a subcomplex of the (n-1)-simplex, since each simplex in the complex is determied by its set of vertices. Therefore it embeds affinely in R^(n-1).
Good point, which gets obscured by talking about identifying vertices ...
It seems that by a general position argument you can embed a k- dimensional complex affinely in (2k+1)-space. You just need to make sure that a bunch of linear subspaces don't have
Something gone missing here! But yes, e.g. a complex of vertices and edges is surely embeddable in 3-space. Since this number is one greater than the dimension in the theorem Dan quoted about embedding a k-manifold, is it possible to employ a similar argument to prove it?
I should have added that if you have a countable d-dimensional simplicial complex, then a random map of the vertices into R^(2d+1) extends to an affine embedding. Bill
Is this obvious [tho not to me] or are you quoting a theorem? Does d = k here? WFL
On Nov 24, 2006, at 8:54 PM, Fred lunnon wrote:
I should have added that if you have a countable d-dimensional simplicial complex, then a random map of the vertices into R^(2d+1) extends to an affine embedding. Bill
Is this obvious [tho not to me] or are you quoting a theorem? Does d = k here? WFL
This is obvious once you've met an argument of this sort. It's a generalization of the assertion that if m <= n, then there is a subset of m-tuples of vectors in R^n that are linearly independent, i.e. the rank of a random mXn matrix is min (m,n)---which easily follows from induction, if you have (m-1) linearly independent vectors, then the mth just has to avoid an m-dimensional plane spanned by the others. From this it follows that a random (k)-dimensional subspace and a random (m-k)-dimensional subspace intersect only at the origin --- just use the first k of your m-tuple to give one subspace, and the last (m-k) to give the other. If we switch to affine subspaces, algebraically given by linear combinations of vectors where the sum of the coefficients is 1, then the same argument says that a random set of (n+1) vectors is affinely independent, and two random affine subspaces of R^n whose dimensions sum to less than n are disjoint. More generally, if you look at pairs of affine subspaces A and B at random subject to the condition that there intersection contains a third subspace C, then if dim(A) + dim(B) - dim(C) < n there is a set of full measure that intersects only in C. So, among countable sequences of points in R^n, there is a subset of full measure such that all affine subspaces spanned by k-tuples are disjoint, provided k < n/ 2. This gives an embedding of any k-dimensional simplicial complex with vertex set these points. The set where this condition holds is also "generic" or Baire second category: an intersection of open dense subsets. Bill
On 11/25/06, Bill Thurston <wpt4@cornell.edu> wrote:
On Nov 24, 2006, at 8:54 PM, Fred lunnon wrote:
I should have added that if you have a countable d-dimensional simplicial complex, then a random map of the vertices into R^(2d+1) extends to an affine embedding. Bill
Is this obvious [tho not to me] or are you quoting a theorem? Does d = k here? WFL
This is obvious once you've met an argument of this sort. ...
Sure --- once I'd managed to fill in the line missing from the previous post, I realised what you'd been trying to say. All the same, I'd like to see some more work to provide a geometric or algebraic construction. For example, each time we need to choose a new vertex, we can make it the centroid of one of the convex hulls into which the set of all primes (hyperplanes) partitions the space; except for multiple intersections at the previously chosen vertices, all these hulls have properly of maximum dimension, by induction. Alternatively, we might ask for an explicit d x oo matrix such that every subset of d rows has maximum rank. I can't see how to do this off-hand. Finally, turning a previous comment on its head, this result seems to give a very cheap proof of a weaker version of the manifold embedding theorem: just triangulate a d-manifold arbitrarily densely, then continuity ensures it can be embedded in (2d+1)-space! [Have I overlooked anything here?] Now then, how might the extra dimension be unloaded, I wonder ... Fred Lunnon
There's a construction using Vandermonde determinants: look at the Vandermonde curve t -> ( t, t^2, t^3, ..., t^n) in R^n, or for symmetry of computation, put it in a hyperplane in R^(n+1), t -> ( 1, t, t^2, t^3, ..., t^n). For any n+1 distinct points, the determinant of the associated (n+1)X (n+1) matrix is non-zero. This determinant is the volume of the simplex spanned by the points times (n+1)! Therefore, for k <= n, any k points on the Vandermonde curve are affinely independent. Bill On Nov 25, 2006, at 11:29 AM, Fred lunnon wrote:
Alternatively, we might ask for an explicit d x oo matrix such that every subset of d rows has maximum rank. I can't see how to do this off- hand.
This morning, I even thought about a paper of McMullen's on the upper bound conjecture, where he uses exactly that construction. As Bill Gosper would say --- duh! WFL On 11/25/06, Bill Thurston <wpt4@cornell.edu> wrote:
There's a construction using Vandermonde determinants: look at the Vandermonde curve t -> ( t, t^2, t^3, ..., t^n) in R^n, or for symmetry of computation, put it in a hyperplane in R^(n+1), t -> ( 1, t, t^2, t^3, ..., t^n). For any n+1 distinct points, the determinant of the associated (n+1)X (n+1) matrix is non-zero. This determinant is the volume of the simplex spanned by the points times (n+1)! Therefore, for k <= n, any k points on the Vandermonde curve are affinely independent. Bill On Nov 25, 2006, at 11:29 AM, Fred lunnon wrote:
Alternatively, we might ask for an explicit d x oo matrix such that every subset of d rows has maximum rank. I can't see how to do this off- hand.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (4)
-
Bill Thurston -
Bill Thurston -
Daniel Asimov -
Fred lunnon