Goto Chapter: Top 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 Bib Ind
 [Top of Book]  [Contents]   [Previous Chapter]   [Next Chapter] 

2 Theoretical foundations
 2.1 Polytopes and polytopal complexes
 2.2 Simplices and simplicial complexes
 2.3 From geometry to combinatorics
 2.4 Discrete Normal surfaces
 2.5 Polyhedral Morse theory and slicings
 2.6 Discrete Morse theory
 2.7 Tightness and tight triangulations
 2.8 Simplicial blowups

2 Theoretical foundations

The purpose of this chapter is to recall some basic definitions regarding polytopes, triangulations, polyhedral Morse theory, discrete normal surfaces, slicings, tight triangulations and simplicial blowups. The expert in these fields may well skip to the next chapter.

For a more detailed look the authors recommend the books [Hud69], [RS72] on PL-topology and [Zie95], [Gr{03] on the theory of polytopes.

An overview of the more recent developments in the field of combinatorial topology can be found in [Lut05] and [Dat07].

2.1 Polytopes and polytopal complexes

A convex d-polytope is the convex hull of n points p_i ∈ E^d in the d-dimensional euclidean space:

P= conv \{v_1,\dots,v_n\}\subset E^d,

where the v_1,dots,v_n do not lie in a hyperplane of E^d.

From now on when talking about polytopes in this document always convex polytopes are meant unless explicitly stated otherwise.

For any supporting hyperplane h ⊂ E^d, P∩ h is called a k-face of P if dim(P∩ h)=k. The 0-faces are called vertices, the 1-faces edges and the (d-1)-faces are called facets of P.

A d-polytope P for which all facets are congruent regular (d-1)-polytopes and for which all vertex links are congruent regular (d-1)-polytopes is called regular, where the regular 2-polytopes are regular polygons.

The set of all k-faces of P is called the k-skeleton of P, written as skel_k(P).

A polytopal complex C is a finite collection of polytopes P_i, 1 ≤ i ≤ n for which the intersection of any two polytopes P_i ∩ P_j is either empty or a common face of P_i and P_j. The polytopes of maximal dimension are called the facets of C. The dimension of a polytopal complex C is defined as the maximum over all dimensions of its facets.

For every d-dimensional polytopal complex the (d+1)-tuple, containing its number of i-faces in the i-th entry is called the f-vector of the polytopal complex.

Every polytope P gives rise to a polytopal complex consisting of all the proper faces of P. This polytopal complex is called the boundary complex C(∂ P) of the polytope P.

2.2 Simplices and simplicial complexes

A d-dimensional simplex or d-simplex for short is the convex hull of d+1 points in E^d in general position. Thus the d-simplex is the smallest (with respect to the number of vertices) possible d-polytope. Every face of the d-simplex is a m-simplex, m ≤ d.

A 0-simplex is a point, a 1-simplex is a line segment, a 2-simplex is a triangle, a 3-simplex a tetrahedron, and so on.

A polytopal complex which entirely consists of simplices is called a simplicial complex (for this it actually suffices that the facets (i. e., the faces that are not included in any other face of the complex) of a polytopal complex are simplices).

The dimension of a simplicial complex is the maximal dimension of a facet. A simplicial complex is said to be pure if all facets are of the same dimension. A pure simplicial complex of dimension d satisfies the weak pseudomanifold property if every (d-1)-face is part of exactly two facets.

Since simplices are polytopes and, hence, simplicial complexes are polytopal complexes all of the terminology regarding simplicial complexes can be transfered from polytope theory.

2.3 From geometry to combinatorics

Every d-simplex has an underlying set in E^d, as the set of all points of that simplex. In the same way one can define the underlying set |C| of a simplicial complex C. If the underlying set of a simplicial complex C is a topological manifold, then C is called triangulated manifold (or triangulation of |C|).

One can also go the other way and assign an abstract simplicial complex to a geometrical one by identifying each simplex with its vertex set. This obviously defines a set of sets with a natural partial ordering given by the inclusion (a socalled poset).

Let v be a vertex of C. The set of all facets that contain v is called star of v in C and is denoted by star_C(v). The subcomplex of star_C(v) that contains all faces not containing v is called link of v in C, written as lk_C(v).

A combinatorial d-manifold is a d-dimensional simplicial complex whose vertex links are all triangulated (d-1)-dimensional spheres with standard PL-structure. A combinatorial pseudomanifold is a simplicial complex whose vertex links are all combinatorial (d-1)-manifolds.

Note that every combinatorial manifold is a triangulated manifold. The opposite is wrong: for example, there exists a triangulation of the 5-sphere that is not combinatorial, the so called Edward's sphere, see [BL00].

A combinatorial manifold carries an induced PL-structure and can be understood in terms of an abstract simplicial complex. If the complex has d vertices there exists a natural embedding of C into the (d-1) simplex and, thus, into E^d-1. In general, there is no canonical embedding into any lower dimensional space. However, combinatorial methods allow to examine a given simplicial complex independently from an embedding and, in particular, independently from vertex coordinates.

Some fundamental properties of an abstract simplicial complex C are the following:

Dimensionality.

The dimension of C.

f, g and h-vector.

The f-vector (f_k equals the number of k-faces of a simplicial complex), the g- and h-vector can be obtained from the f-vector via linear transformations.

(Co-)Homology.

The simplicical (co-)homology groups and Betti numbers.

Euler characteristic

The Euler characteristic as the alternating sum over the Betti numbers / the f-vector.

Connectedness and closedness.

Whether C is strongly connected, path connected, has a boundary or not.

Symmetries.

The automorphism group, i. e. the group of all permutations on the set of vertex labels that do not change the complex as a whole.

All of those properties and many more can be computed on a strictly combinatorial basis.

2.4 Discrete Normal surfaces

The concept of normal surfaces is originally due to Kneser [Kne29] and Haken [Hak61]: A surface S, properly embedded into a 3-manifold M, is said to be normal, if it respects a given cell decomposition of M in the following sense: It does not intersect any vertex nor touch any 3-cell of the manifold and does not intersect with any 2-cell in a circle or an arc starting and ending in a point of the same edge. Here we will look at normal surfaces in the case that M is given as a combinatorial 3-manifold and we will call the corresponding objects discrete normal surfaces. In order to do this let us first define:

Definition
A polytopal manifold is a polytopal complex M such that there exists a simplicial subdivision of M which is a combinatorial manifold. If M is a surface we will call it a polytopal map. If, in addition M entirely consists of m-gons, we call it a polytopal m-gon map.

Definition (Discrete Normal surface, [Spr11b])
Let M be a combinatorial 3-manifold (3-pseudomanifold), ∆ ∈ M one of its tetrahedra and P the intersection of with a plane that does not include any vertex of . Then P is called a normal subset of . Up to an isotopy that respects the face lattice of , P is equal to one of the triangles P_i, 1 ≤ i ≤ 4, or quadrilaterals P_i, 5 ≤ i ≤ 7, shown in Figure 7.

A polyhedral map S ⊂ M that entirely consists of facets P_i such that every tetrahedron contains at most one facet is called discrete normal surface of M.

The second author has recently investigated on the combinatorial theory of discrete normal surfaces, see [Spr11b].

2.5 Polyhedral Morse theory and slicings

In the field of PL-topology Kühnel developed what one might call a polyhedral Morse theory (compare [K{\95], not to be confused with Forman's discrete Morse theory for cell complexes which is decribed in Section 2.6):

Let M be a combinatorial d-manifold. A function f:M -> R is called regular simplexwise linear (rsl) if f(v) ≠ f(w) for any two vertices w ≠ v and if f is linear when restricted to an arbitrary simplex of the triangulation.

A vertex x ∈ M is said to be critical for an rsl-function f:M -> R, if H_⋆ (M_x , M_x backslash { x } , F) ≠ 0 where M_x := { y ∈ M | f(y) ≤ f(x) } and F is a field.

It follows that no point of M can be critical except possibly the vertices. In arbitrary dimensions we define:

Definition (Slicing, [Spr11b])
Let M be a combinatorial pseudomanifold of dimension d and f:M -> R an rsl-function. Then we call the pre-image f^-1 (α) a slicing of M whenever α ≠ f(v) for any vertex v ∈ M.

By construction, a slicing is a polytopal (d-1)-manifold and for any ordered pair α ≤ β we have f^-1 (α) ≅ f^-1 (β) whenever f^-1([α,β]) contains no vertex of M. In particular, a slicing S of a closed combinatorial 3-manifold M is a discrete normal surface: It follows from the simplexwise linearity of f that the intersection of the pre-image with any tetrahedron of M either forms a single triangle or a single quadrilateral. In addition, if two facets of S lie in adjacent tetrahedra they either are disjoint or glued together along the intersection line of the pre-image and the common triangle.

Any partition of the set of vertices V = V_1 dot∪ V_2 of M already determines a slicing: Just define an rsl-function f: M -> R with f(v) ≤ f(w) for all v ∈ V_1 and w ∈ V_2 and look at a suitable pre-image. In the following we will write S_(V_1,V_2) for the slicing defined by the vertex partition V = V_1 dot∪ V_2.

Every vertex of a slicing is given as an intersection point of the corresponding pre-image with an edge ⟨ u,w ⟩ of the combinatorial manifold. Since there is at most one such intersection point per edge, we usually label this vertex of the slicing according to the vertices of the corresponding edge, that is binomuw with u ∈ V_1 and w ∈ V_2.

Every slicing decomposes the surrounding combinatorial manifold M into at least 2 pieces (an upper part M^+ and a lower part M^-). This is not the case for discrete normal surfaces (see 2.4) in general. However, we will focus on the case where discrete normal surfaces are slicings and we will apply the above notation for both types of objects.

Since every combinatorial pseudomanifold M has a finite number of vertices, there exist only a finite number of slicings of M. Hence, if f is chosen carefully, the induced slicings admit a useful visualization of M, c.f. [SK11].

2.6 Discrete Morse theory

For an introduction into Forman's discrete Morse theory see [For95], not to be confused with Banchoff and Kühnel's theory of regular simplexwise linear functions which is described in Section 2.5).

2.7 Tightness and tight triangulations

Tightness is a notion developed in the field of differential geometry as the equality of the (normalized) total absolute curvature of a submanifold with the lower bound sum of the Betti numbers [Kui84], [BK97]. It was first studied by Alexandrov, Milnor, Chern and Lashof and Kuiper and later extended to the polyhedral case by Banchoff [Ban65], Kuiper [Kui84] and Kühnel [K{\95]. From a geometrical point of view, tightness can be understood as a generalization of the concept of convexity that applies to objects other than topological balls and their boundary manifolds since it roughly means that an embedding of a submanifold is ``as convex as possible'' according to its topology. The usual definition is the following:

Definition (Tightness, [K{\95])
Let F be a field. An embedding M → E^N of a compact manifold is called k-tight with respect to F if for any open or closed halfspace h⊂ E^N the induced homomorphism

H_i(M\cap h;\mathbb{F})\longrightarrow H_i(M;\mathbb{F})

is injective for all i≤ k. M is called F-tight if it is k-tight for all k. The standard choice for the field of coefficients is F_2 and an F_2-tight embedding is called tight.

With regard to PL embeddings of PL manifolds tightness of combinatorial manifolds can also be defined via a purely combinatorial condition as follows. For an introduction to PL topology see [RS72].

Definition (Tight triangulation [K{\95])
Let F be a field. A combinatorial manifold K on n vertices is called (k-) tight w.r.t. F if its canonical embedding K⊂ ∆^n-1⊂ E^n-1 is (k-)tight w.r.t. F, where ∆^n-1 denotes the (n-1)-dimensional simplex.

In dimension d=2 the following are equivalent for a triangulated surface S on n vertices: (i) S has a complete edge graph K_n, (ii) S appears as a so called regular case in Heawood's Map Color Theorem [Rin74], compare [K{\95] and (iii) the induced piecewise linear embedding of S into Euclidean (n-1)-space has the two-piece property [Ban74], and it is tight [K{\95].

Kühnel investigated the tightness of combinatorial triangulations of manifolds also in higher dimensions and codimensions, see [K{\94]. It turned out that the tightness of a combinatorial triangulation is closely related to the concept of Hamiltonicity of a polyhedral complexes (see [K{\95]): A subcomplex A of a polyhedral complex K is called k-Hamiltonian if A contains the full k-dimensional skeleton of K (not to be confused with the notion of a k-Hamiltonian graph). This generalization of the notion of a Hamiltonian circuit in a graph seems to be due to C.Schulz [Sch94]. A Hamiltonian circuit then becomes a special case of a 0-Hamiltonian subcomplex of a 1-dimensional graph or of a higher-dimensional complex.

A triangulated 2k-manifold that is a k-Hamiltonian subcomplex of the boundary complex of some higher dimensional simplex is a tight triangulation as Kühnel [K{\95] showed. Such a triangulation is also called (k+1)-neighborly triangulation since any k+1 vertices in a k-dimensional simplex are common neighbors. Moreover, (k+1)-neighborly triangulations of 2k-manifolds are also referred to as super-neighborly triangulations -- in analogy with neighborly polytopes the boundary complex of a (2k+1)-polytope can be at most k-neighborly unless it is a simplex. Notice here that combinatorial 2k-manifolds can go beyond k-neighborliness, depending on their topology.

Whereas in the 2-dimensional case all tight triangulations of surfaces were classified by Ringel and Jungerman and Ringel, in dimensions d≥ 3 there exist only a finite number of known examples of tight triangulations (see [KL99] for a census) apart from the trivial case of the boundary of a simplex and an infinite series of triangulations of sphere bundles over the circle due to Kühnel [K{\95], [K{\86].

2.8 Simplicial blowups

The blowing up process or Hopf σ-process can be described as the resolution of nodes or ordinary double points of a complex algebraic variety. This was described by H.~Hopf in [Hop51], compare [Hir53] and [Hau00]. From the topological point of view the process consists of cutting out some subspace and gluing in some other subspace. In complex algebraic geometry one point is replaced by the projective line CP^1 ≅ S^2 of all complex lines through that point. This is often called blowing up of the point or just blowup. In general the process can be applied to non-singular 4-manifolds and yields a transformation of a manifold M to M # (+CP^2) or M # (-CP^2), depending on the choice of an orientation. The same construction is possible for nodes or ordinary double points (a special type of singularities), and also the ambiguity of the orientation is the same for the blowup process of a node. Similarly it has been used in arbitrary even dimension by Spanier [Spa56] as a so-called dilatation process.

A PL version of the blowing up process is the following: We cut out the star of one of the singular vertices which is, in the case of an ordinary double point, nothing but a cone over a triangulated RP^3. The boundary of the resulting space is this triangulated RP^3. Now we glue back in a triangulated version mathbfC of a complex projective plane with a 4-ball removed where antipodal points of the boundary are identified. mathbfC is called a triangulated mapping cylinder and by construction its boundary is PL homeomorphic to RP^3.

For a combinatorial version with concrete triangulations, however, we face the problem that these two triangulations are not isomorphic. This implies that before cutting out and gluing in we have to modify the triangulations by bistellar moves until they coincide:

Definition (Simplicial blowup, [SK11])
Let v be a vertex of a combinatorial 4-pseudomanifold M whose link is isomorphic with the particular 11-vertex triangulation of RP^3 which is given by the boundary complex of the triangulated mathbfC given in [SK11]. Let ψ : operatornamelk(v) → ∂mathbfC denote such an isomorphism. A simplicial resolution of the singularity v is given by the following construction M ↦ widetildeM := (M ∖ operatornamestar(v)^∘) ∪_ψ mathbfC.

The process is described in more detail in [SK11]. In particular it is used to transform a 4-dimensional Kummer variety into a K3 surface.

 [Top of Book]  [Contents]   [Previous Chapter]   [Next Chapter] 
Goto Chapter: Top 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 Bib Ind

generated by GAPDoc2HTML