# Graph theoretic view on manifold triangulations

To make the question (hopefully) clearer, I reformulated it:

Some triangulation $T$ of a smooth manifold $M$ is a piecewise linear manifold, because smooth manifolds are topological manifolds. Such a triangulation is homeomorphic to the smooth manifold, with some homeomorphism $h: T\rightarrow M$. A PL manifold is defined by the property, that the link of any simplex is a PL sphere or in other words the link is homeomorphic to a sphere. If one takes the 1-skeleton of $T$, one gets a graph $G$. I am curious about the equivalent properties of such a full simplicial complex $T$ and its 1-skeleton $G$:

1. Are $G$ and $T$ basically equivalent? In general $T$ should be reconstructible from $G$ (since the simplices form cliques).
2. If so, what properties of $G$ are equivalent to the fact, that the link of any simplex in $T$ is homeomorphic to a sphere?
3. Aren't PL manifolds with that property automatically closed? As far as I understand, the link of a vertex on the boundary of a triangulation cannot be a PL sphere.
4. If so, triangulations of smooth manifolds with a boundary would be excluded. If one wants to include triangulations of such manifolds, what would be the defining property of the PL manifold?

These questions raised in the context of coloring the vertexes of some $T$, to get independend sets of them. If the 1-skeleton is equivalent to some certain type of graph, it may be possible to use optimal algorithms from graph theory.

• What definition of "triangulation of a manifold" are you using? The ordinary definition requires that the triangulation be a simplicial complex, in which case your requirement---that the intersection of two simplices of dimension $d$ have an intersection of dimension $<d$ or none at all---is true by definition. This leads me to assume that by a "triangulation" you mean something else, but I cannot guess what. Commented Jun 8, 2014 at 17:00
• Yes your completely right, I wasn't quite clear on that point. The idea is, that I get as an input a supposed triangulation of some arbitrary manifold. Instead of assuming that this triangulation hasn't any flaws, I want to check it in the first place prior to any computations. This lead me to the idea to use graph theory to check if the defining properties are fulfilled. I think in this way, it makes more sense. Commented Jun 8, 2014 at 17:47
• That makes a little more sense, and yet the question remains hard to answer without knowing in more detail what kind of structure you get as an input. I'll hazard a guess: Are you assuming that only a 1-dimensional simplicial complex is given, i.e. only the 0-simplices and 1-simplices of some putative triangulated $d$-manifold? If so, or if your assumption can be made precise in some such manner, I suggest editing your question. Commented Jun 8, 2014 at 18:03
• Sorry, I'm new to these topics and trying to get into the stuff. I will try to be more specific. Let's restrict to smooth n-manifolds with n >= 2, so we get flat or curved simplicial complexes as triangulations, which inherit the topology. To be even more specific, I want to create triangulations of different 3-manifolds, check their consistency in an equal way and start computations on this complexes. Commented Jun 8, 2014 at 18:13

Questions 1 and 2: This is still a little hard to answer since the meaning of "equivalence" or "reconstruction" is not specified. Here's one possible interpretation, but with a negative answer.

There is a functorial construction which assigns to each simplicial 1-complex a simplicial complex (without restriction on dimension) called its "flag complex": for each subcomplex isomorphic to the boundary of a $k$-simplex you attach a $k$-simplex. But, it is quite false to say that a triangulated manifold is the flag complex of its 1-skeleton. For example it is easy to triangulate the 2-sphere to have three edges in a cycle with no corresonding 2 simplex.

Edit: Here is a construction of an example. Let $S_0$ and $S_1$ be two triangulated spheres (all triangulations are simplicial complexes). Let $\sigma_i \subset S_i$, $i=0,1$ be 2-simplices. Removing the interiors of these simplices we get $D_i = S_i - int(\sigma_i)$ which is a 2-disc, and whose boundary $\partial D_i$ is a cycle of 3-edges (a clique of 3 vertices). Now form a quotient space of $D_0 \cup D_1$ by gluing the boundaries $\partial D_0$ and $\partial D_1$ using a simplicial isomorphism. The quotient is another triangulated 2-sphere $S$, containing a clique of 3 vertices which is not contained in any simplex. This construction can be thought as a "simplicial connected sum" of triangulated 2-spheres.

Perhaps what you really want to know is whether there exist nonisomorphic triangulated $n$-manifolds with isomorphic 1-skeleta, and here I am unsure.

Questions 3 and 4: You are correct that this definition of triangulated manifold precludes boundary. However, the definition can be easily extended to bounded $n$-manifolds by requiring that the link of a boundary point be a PL $n-1$-disc.

Keep in mind also that "closed" usually means "compact and with no boundary", but the theory of triangulated manifolds certainly includes noncompact manifolds.

• Thanks for your answer, but I don't get your example of the 2-sphere. Three edges in a cycle wouldn't (in general) form a clique, but the vertices and their connecting edges of a triangle do so. But maybe I'm just misunderstanding. This would split in two problematic cases: first, the 1-skeleton does have cliques without corresponding simplices (which seems to be the case of your example) or some simplices of the triangulation have no corresponding clique in the 1-skeleton. If you know any good literature about triangulations (e.g. for smooth 3-manifolds), I would be glad to know. Commented Jun 17, 2014 at 16:24
• @L.G.F. Your second problematic case does not occur: in a simplicial complex, the $1$-skeleton of an $n$-dimensional simplex is a clique of $n+1$ points. Commented Jun 23, 2014 at 14:22
• @L.G.F. The first problematic case is indeed what I am referring to: it is quite possible for a triangulated 2-sphere to have a clique of 3 points---what I called "three edges in a cycle"---which is not the 1-skeleton of any 2-dimensional simplex of the triangulation. Commented Jun 23, 2014 at 14:23
• @L.G.F. I shall add an explicit construction to my answer. Commented Jun 23, 2014 at 14:26
• Very nice answer! Now it is clear to me, a even simpler example of this kind would be the boundary of two tetrahedrons glued together at one of their faces. Commented Jul 12, 2014 at 0:35