Defining discrete Morse functions on infinite surfaces

Defining discrete Morse functions on infinite surfaces R. Ayala a, L.M. Fern´andez a, J.A. Vilches a aDpto. de Geometr´ıa y Topolog´ıa, Universidad de Sevilla, 41080, SPAIN Abstract We present an algorithm which defines a discrete Morse function in Forman’s sense on an infinite surface including a study of the minimality of this function. Key words: discrete Morse function, infinite surface, critical point, Morse inequalities 1. Introduction Under a classical or smooth point of view, Morse theory looks for links between global properties of a smooth manifold and critical points of a function defined on it. In [2], Forman introduced the notion of discrete Morse function defined on a finite cw-complex and, in this combinatorial context, he developed a discrete Morse theory as a tool for studying the homotopy type and homology groups of these complexes. Once a Morse function has been defined on a complex, then its topological information can be deduced from the critical simplices of this function. Since we studied the problem concerning the definition of discrete Morse functions on infinite 1complexes in other works [1,4], the goal of this paper is to continue with the following natural step: to develop a way of constructing discrete Morse functions on infinite 2-complexes, in particular on connected and non compact surfaces. Our methods are based on algorithms developed by T. Lewiner [3] for the finite case. Given a simplicial complex M, R. Forman [2] introduces the notion of discrete Morse function as a function f:M−→ Rsuch that, for any psimplex σ∈M: (M1) card{τ(p+1) > σ/f(τ)≤f(σ)} ≤ 1. Email addresses: [email protected] (L.M. Fern´andez ), [email protected] (J.A. Vilches ). 1This work is partially supported by P.A.I. (M2) card{υ(p−1) < σ/f(υ)≥f(σ)} ≤ 1. Ap-simplex σ∈Mis said to be critical with respect to fif: (C1) card{τ(p+1) > σ/f(τ)≤f(σ)}= 0. (C2) card{υ(p−1) < σ/f(υ)≥f(σ)}= 0. 2. Constructing discrete Morse functions In order to define a discrete Morse function on an infinite surface Swe recall that it can be expressed as a countable union of finite subcomplexes S=∪n∈NKn, with Kn⊆Kn+1 for any n∈N. Indeed, let v0be any vertex of a triangulation of Sand let K1be the closed star of v0, that is, the smallest closed subcomplex of Swhich contains all edges and triangles including v0. The following figure shows the closed star of v0in continous lines. v0 Fig. 1. Star of v0. 20th EWCG Seville, Spain (2004) 20th European Workshop on Computational Geometry To define the rest of subcomplexes Kn, we can do a successive thickening of K1:K2will be the closed star of K1and, in the general case, Knwill be the closed star of Kn−1, where the closed star of a subcomplex means the smallest closed subcomplex that contains all edges and triangles which contain some simplex of the given subcomplex. Next, we shall use a special graph which contains information of part of any Kn, in which all triangles and some edges of Kare represented. If T1 is a spanning tree in K1, then the complementary graph of T1in K1, denoted by D1, is the graph constructed as follows: each vertex of D1corresponds to a triangle of K1or to a bounding edge of K1 (that is, an edge which is in a unique triangle of K1 and not in T1) and there is an edge between two vertices of D1if these ones correspond to two triangles sharing an edge or to a triangle and a bounding edge which is in this triangle but not in T1. Considering the preceding figure, D1is the graph drawed with discontinous lines in the following figure: v0 1 Fig. 2. D1. Now we enlarge the spanning tree T1until we get a spanning tree T2in K2. Then, we obtain D2as an enlargement of D1and it is the complementary graph of T2in K2. We can continue this process in successive steps. It is interesting to point out that this construction is only possible for 2-dimensional complexes because the union of Tnand Dncovers whole Kn, for any n∈N. The definition of a discrete Morse function f on Sstarts with the definition of fin K1. This process is divided in two steps: first, we define f on a spanning tree T1in K1starting at v0. This assignment is made by an increasing way and such that we do not introduce any critical vertex or edge but the vertex v0, which is a global minimum and hence it is a critical vertex [4]. On the other hand, in order to complete the definition of fon the whole K1, we shall need to define fon D1. To this end, we define the degree of a vertex corresponding to a triangle as the number of edges which are in this triangle such that we have not assigned them any value. Since Sis a surface, the degree of any vertex is a number between 0 and 3. Now we start the definition of f on vertices of degree 1 assigning them the greatest value of fon T1plus one unit. This means that we have assigned that value to the triangles of K1 corresponding to such vertices of degree one. Next, we assign the same value to the free (no values assigned) edges of such triangles. Then, we re-write the degrees of the vertices of D1because they could have changed and continue assigning values to vertices of degree one by increasing in one unit until finishing with all vertices of D1. See the following figure as an example. 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 Fig. 3. fon K1. Now, to extend fto the subcomplex K2, we repeat the increasing procedure to assign values of f on T2−T1and on D2−D1. Since this procedure is well defined for any n∈N, it gives us a function f defined on whole surface S. It’s important to point out that in this process may appear situations in which there are no degree one vertices in a Dn. It implies that the corresponding edges are in a cycle of non assigned edges. 3. Study of f The following result states that the above defined function fis a discrete Morse function in March 25-26, 2004 Seville (Spain) Forman’s sense and give us information about its critical elements. Proposition. The function fgiven by the preceding procedure is a discrete Morse function defined on the infinite surface Sand has a unique critical vertex, the initial vertex v0, as many critical edges as many independent cycles of non assigned edges are found and do not have any critical triangle. References [1] R. Ayala, L.M. Fern´andez and J.A. Vilches, Desigualdades de Morse generalizadas sobre grafos, Actas de las III jornadas de Matem´atica Discreta y Algor´ıtmica (Universidad de Sevilla, Spain, 2002) 159– 164. [2] R. Forman, Morse Theory for cell complexes, Adv. in Math. 134 (1998) 90-145. [3] T. Lewiner, G. Tavares and H. Lopes. Optimal Morse-Forman functions for combinatorial 2-manifolds, to appear in Computational Geometry: Theory and Applications (2003). [4] J.A. Vilches, Funciones de Morse discretas sobre complejos infinitos, book (Edici´on Digital @tres, Sevilla, 2003).