From: asimov@durban.berkeley.edu (Daniel Asimov) Newsgroups: sci.math.research Subject: Higher-Dimensional Version of Graph Planarity Criterion??? Date: 18 Sep 1996 18:05:03 GMT According to Kuratowski, a finite graph (nodes and edges) can be topologically embedded in the plane if and only if it does not contain either of two "forbidden" subgraphs (the complete graph on 5 vertices, and the water-gas- electricity graph). Now instead suppose we have a simplicial complex K that is the union of 2-simplices. Does there exist a similar theorem giving conditions for when |K| can be topologically embedded in R^3 ??? In generality, let K be a simplicial complex that is the union of p-simplices. Are there criteria for when |K| can be topologically embedded in R^n ??? Any references to the literature would be appreciated. --Dan Asimov ============================================================================== From: greg@math.math.ucdavis.edu (Greg Kuperberg) Newsgroups: sci.math.research Subject: Re: Higher-Dimensional Version of Graph Planarity Criterion??? Date: 19 Sep 1996 01:02:30 GMT In article <51pdkf\$agc@agate.berkeley.edu> asimov@durban.berkeley.edu (Daniel Asimov) writes: >Now instead suppose we have a simplicial complex K that is the union of >2-simplices. Does there exist a similar theorem giving conditions for when >|K| can be topologically embedded in R^3 ??? Yes and no. It's extremely unlikely that there will ever be a pithy condition analogous to Kuratowski's theorem. The status of an interesting special case illustrates why. The link of any vertex in K is some graph which has to be planar for for such an embedding to exist. Suppose for simplicity that this embedding is unique for all vertices. Then you know the cyclic ordering of faces coming into each edge, and if these cyclic orderings are consistent, you can thicken K to get a 3-manifold with boundary. So far everything is easy to check. Now suppose for simplicity that when you thicken K, all boundary components are spheres. Plugging the holes, you are reduced to deciding whether a given triangulated 3-manifold is S^3. Until a few years ago, it was not known whether this question is recursive, i.e. whether there exists any algorithm at all to decide whether you have S^3. (In fact it's a theorem that there is no algorithm to recognize S^5.) But now there is an algorithm due to Hyam Rubinstein that fits the bill. Sketch of the algorithm: A surface in a triangulated 3-manifold is normal if and only if it intersects each tetrahedron in triangles and quadrilaterals. It is almost normal if in one simplex there is an octagon which meets each face twice. The algorithm dictates that you should first look for a maximal collection of disjoint, non-parallel normal spheres. The manifold is a 3-sphere if and only if each region bounded by exactly two normal spheres possesses an almost normal sphere. Reference: Thompson, Thin position and Rubinstein's solution to the recognition problem for S3, Mathematical Research Letters, 1, (1994) -- /\ Greg Kuperberg / \ Department of Mathematics, UC Davis \ / greg@math.ucdavis.edu \/ http://www.math.ucdavis.edu/~greg