Hi, is there an algorithm that determines if a given simplicial complex is a.) a manifold b.) a smooth manifold c.) homotopy equivalent to a manifold d.) a real algebraic variety
?
$\begingroup$
$\endgroup$
3
-
2$\begingroup$ There is not really a big difference between (b) and (d) since every compact differentiable manifold is a real algebraic variety as cited in aimsciences.org/journals/pdfs.jsp?paperID=2431&mode=full [a result due to Nash and Tognoli] $\endgroup$– Lennart MeierCommented Jul 27, 2011 at 14:10
-
4$\begingroup$ All finite simplicial complexes have the homotopy-type of manifolds, provided you allow the manifolds to have boundary. The proof is given by embedding the simplicial complex in a suitably high-dimensional manifold (say Euclidean space) and then taking a smooth regular neighbourhood of the complex. The regular neighbourhood has the same homotopy-type and it's a smooth manifold. $\endgroup$– Ryan BudneyCommented Jul 27, 2011 at 17:10
-
$\begingroup$ Any manifold with boundary has the homotopy type of a manifold without boundary, so you don't need that requirement... $\endgroup$– Dylan WilsonCommented Feb 15, 2013 at 16:39
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
12
A simplicial complex is a manifold if the links of all vertices are simplicial spheres. Recognizing the $n$-sphere is easy for $n=1, 2$, tractable for $n=3$ (the Rubinstein-Thompson algorithm and refinements thereof. I believe it is still exponential time), and undecidable for $n\geq 5$ by a result of Novikov -- see http://www.inf.ethz.ch/personal/wagneru/Manuscripts/e4hard.pdf and references therein. Don't know about $n=4.$
As for "real algebraic variety", every manifold is homotopy equivalent to a real algebraic variety (this is Nash's famous theorem), and every manifold of dimension less than 10 is homeomorphic to a real algebraic variety (see http://www.ams.org/journals/bull/1977-83-02/S0002-9904-1977-14307-3/S0002-9904-1977-14307-3.pdf), so in those dimensions your last question collapses to your first question.
EDIT As pointed out by @Lennart Meier in his comment, in fact, every smooth manifold is homeomorphic to a real algebraic variety.
answered Jul 27, 2011 at 14:32
-
$\begingroup$ thanks, however not every algebraic variety is a manifold (figure 8) and not every semi algebraic set is a variety Could you give a hint to: A simplicial complex is a manifold if the links of all vertices are simplicial spheres. $\endgroup$ Commented Jul 27, 2011 at 14:46
-
2$\begingroup$ @unknown, hint: the star is the cone on the link. Also problematic is that not every manifold is PL: there are triangulated manifolds with links that are not spheres. $\endgroup$ Commented Jul 27, 2011 at 14:52
-
4$\begingroup$ Hey Igor, I'm voting this down because not every manifold of dimension 10 is homeomorphic to a real algebraic variety, for example a simply-connected 4-manifold with $E_8$ intersection form: en.wikipedia.org/wiki/4-manifold Also, as Richard points out, there are manifolds which have a simplicial structure with links of vertices not spheres (like the double suspension of a homology 3-sphere). So although you are correct in saying that if the links of vertices are spheres, it is a manifold, this does not imply that there is no algorithm to tell if it is a manifold. $\endgroup$– Ian AgolCommented Jul 28, 2011 at 0:50
-
3$\begingroup$ As Richard Kent says, this is the criterion for a PL manifold. There is a known weaker condition for it to be a topological manifold. Something like: the links of vertices are simply connected spaces with the homology of the sphere. (2) Undecidability is about the word problem. n=4 should be decidable because the problem is the links, which are 3-manifolds, which have decidable groups. $\endgroup$ Commented Jul 28, 2011 at 3:21
-
1$\begingroup$ @Gil: I don't disagree that the question should be edited (I just need to get around to it), but I don't think there are disagreements, just some confusion about what "manifold" means. I implicitly assumed "PL manifold", but this is obviously not a universal assumption. $\endgroup$ Commented Jul 28, 2011 at 22:33
$\begingroup$
$\endgroup$
3
There is the idea of a simplicial manifold, which works by checking that the complex is pure (all facets of the same dimension) and that each codimension 1 face is included in the correct number of facets.
Beyond this answer to your question a), I believe b) and d) to be potentially really difficult. It would seem to me that almost no simplicial complexes are in themselves smooth (unless you give an explicit embedding, in which case you need to check smoothness for each face separately, or something like that), but that all simplicial manifolds can be deformed into a smooth manifold.
As for c), it seems to reconnect to the criterion for a), but it is not clear to me whether algorithmics exist.
You might want to check out the work by Benjamin Burton.
answered Jul 27, 2011 at 14:06
-
2$\begingroup$ This is usually called a pseudomanifold. It is so much weaker a condition than manifold that I must call this answer wrong. $\endgroup$ Commented Jul 28, 2011 at 3:09
-
$\begingroup$ Novik and Swartz have introduced the notion of a homology manifold, which is much closer to an actual manifold than a pseudo-manifold is, and is an algorithmically checkable condition. See math.washington.edu/~novik/publications/Gorenstein.pdf For dimension $\leq 3$, a homology manifold is a manifold; in dimension $4$, it is a manifold except for finitely many singularities which are cones on homology $3$-spheres. See their paper for lots more. $\endgroup$ Commented Jul 28, 2011 at 11:52
-
$\begingroup$ The term "homology manifold" goes back at least to the 50s, although the term "generalized manifold" was more popular for decades. $\endgroup$ Commented Jul 28, 2011 at 16:32
$\begingroup$
$\endgroup$
1
(b) When does a PL manifold have a smooth structure?
I believe that this is computable. Smoothing theory, closely related to the Hirsch-Smale immersion theory (an h-principle), identifies the set of smooth structures on a PL manifold with the set vector bundles that are reasonable candidates for the tangent bundle in the sense that they are reductions of structure group of the PL tangent bundle. The theory of principal bundles reduces to homotopy theory. The set of homotopy classes of maps from a finite complex to a finite complex with abelian fundamental group and the induced maps between such sets are computable, but it is rarely implemented.
-
$\begingroup$ This answer suggests that there is an algorithm to tell if a PL manifold has a smoth structure. However, telling if a simplicial complex is e.g. a PL sphere is known to be undecidable in high dimensions. $\endgroup$ Commented Jul 28, 2011 at 14:47