## When are (finite) simplicial complexes (smooth) manifolds?

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

?

-
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/… [a result due to Nash and Tognoli] – Lennart Meier Jul 27 2011 at 14:10
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. – Ryan Budney Jul 27 2011 at 17:10
Any manifold with boundary has the homotopy type of a manifold without boundary, so you don't need that requirement... – Dylan Wilson Feb 15 at 16:39

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.

-
 This is usually called a pseudomanifold. It is so much weaker a condition than manifold that I must call this answer wrong. – Ben Wieland Jul 28 2011 at 3:09 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/… 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. – David Speyer Jul 28 2011 at 11:52 The term "homology manifold" goes back at least to the 50s, although the term "generalized manifold" was more popular for decades. – Ben Wieland Jul 28 2011 at 16:32

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.

-
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. – Markus Ulke Jul 27 2011 at 14:46
@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. – Richard Kent Jul 27 2011 at 14:52
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. – Agol Jul 28 2011 at 0:50
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. – Ben Wieland Jul 28 2011 at 3:21
@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. – Igor Rivin Jul 28 2011 at 22:33