Teoría de morse discreta

U n i v e r s i d a d d e S e v i l l a – F a c u l t a d d e M a t e m á t i c a s TEORÍA DE MORSE DISCRETA Alejandro Ballesteros Hernández Memoria de Trabajo Fin de Grado Grado en Matemáticas Índice general Abstract 5 Introducción 6 Capítulo 1. Preliminares 8 1.1. Nociones básicas de Homotopía y Homología Simplicial 8 1.2. Teoría de Morse diferenciable 13 Capítulo 2. Teoría de Morse Discreta 17 2.1. Funciones de Morse discretas 17 2.2. Campos Gradientes Discretos 22 2.3. Funciones de Morse óptimas y perfectas. 32 Referencias bibliográcas 39 3 Este trabajo no podría haberse realizado sin la colaboración de muchas personas que me han brindado su ayuda, sus conocimientos y su apoyo. Quiero agradecerles a todos ellos cuanto han hecho por mí, para que este trabajo saliera adelante de la mejor forma posible. Quedo especialmente agradecido por mi director del trabajo Don José Antonio Vilches que me ha apoyado y ayudado en todo momento. Ha corregido minuciosamente este trabajo y me ha dado la posibilidad de mejorarlo. Tengo que agradecerle sus comentarios, direcciones, sugerencias, y las correcciones con las que he podido redactar una memoria adecuada de todo el trabajo realizado en este último curso. A todos los profesores del Departamento de Geometría y Topología que me han dado clase y me han aportado todos los conocimientos sin los cuales no me hubiera decantado por esta rama de las matemáticas. A mis padres José Manuel y Charo, por darme la vida y apoyarme en todo lo que me he propuesto así como por introducirme en las matemáticas a una edad temprana, por ser mi ejemplo a seguir, por enseñarme a seguir aprendiendo todos los días sin importar las circunstancias y el tiempo. Vosotros sois la columna vertebral de toda la formación que tengo y la que tendré en el futuro. Por último y lo más importante, mi más profundo agradecimiento a mi tío y mentor Don Rafael Ayala, que sin su apoyo y colaboración, especialmente en mis días más bajos, no hubiera sido posible concluir esta etapa tan importante de mi formación. 4 Abstract Since it was introduced by Marston Morse in the 1920s, Morse Theory has been one of the most powerful and useful tool for the study of smooth manifolds. Basically, it allows to describe the topology of a manifold in terms of the cellular decomposition generated by the critical points of a scalar smooth map dened on it. In the 1990s Robin Forman developed a combinatorial analog to Morse theory that turned out to be a fruitful and ecient method for studying the homotopy type and homology groups of discrete objects, such as simplicial and cellular complexes. The essential components of Forman's discrete Morse theory are the discrete Morse function and critical símplices. A discrete Morse function assigns values to símplices such that higher-dimensional símplices have higher values than lower-dimensional símplices, with at most one exception, locally, at each simplex. A critical simplex is one near which no such exception occurs. The main reason why these denitions seem to be quite dierent from those of dierential geometry is that they correspond to a natural and easily representable notion of induced discrete vector eld which includes the idea of ow lines ressembling the corresponding notion for smooth vector elds. Roughly speaking, the discrete vector eld induced by a discrete Morse function describe a collapsing process, and is a pairing of the complex, formed by pairs of símplices of two consecutives dimensions on which the function inverts the order given by face inclusion. Then, those símplices that do not belong to any pair are precisely the critical símplices of the map and a combinatorial gradient path is a connected sequence of the pairs on which the function is decreasing. In this work we present the basic notions and results of discrete Morse theory, with emphasis in two aspects: it can be interpreted under a graph-theoretical point of view as a matching in the Hasse diagram of its domain and the special role played by the optimal discrete Morse functions, that is, those with as less critical símplices as possible. For simplicity, we have omitted the proofs of the more technical results that can be found in detail in the cited references. 5 Introducción Esencialmente, la teoría de Morse discreta es una adaptación combinatorial a los CW− complejos nitos de la teoría de Morse diferenciable, que permite simplicar su topología sin cambiar su tipo de homotopía. Recordemos que la teoría de Morse diferenciable fue desarrollada por M. Morse en los años 20, y es una de las herramientas más potentes de la Topología Diferencial, pues proporciona una relación fundamental entre el Análisis y la Topología. Más precisamente, establece que el tipo de homotopía de una variedad es el de un CW− complejo, cuyas células quedan determinadas por los puntos críticos (aquellos en los que se anula el gradiente) de ciertas funciones escalares denidas sobre ellas, que son las funciones de Morse. De hecho, estas funciones pueden interpretarse como un método para construir el complejo celular por conjuntos de nivel, a medida que va creciendo el valor de la función, y los teoremas fundamentales de la teoría muestran que el tipo de homotopía de dichos conjuntos cambia solo cuando se pasa por un valor crítico de la función. Una exposición clásica de la teoría de Morse diferenciable puede encontrarse en el libro de Milnor [9], donde se da la demostración de las desigualdades de Morse, que arman que el número de puntos críticos de cada tipo de función de Morse es cota superior de sus distintos números de Betti. Hacia 1995, en [5] R. Forman lleva estas ideas al contexto discreto (o combinatorio) y desarrolla una teoría de Morse para poliedros completamente discreta, es decir, utilizando solo su estructura celular o simplicial, sin necesidad de recurrir a su topología ni a ninguna noción de continuidad. Tal como aclara Forman, esto no es una teoría totalmente nueva; lo que él logró fue extraer la esencia combinatoria de la teoría clásica para variedades diferenciables, y consiguió probar los resultados análogos a los teoremas básicos de la teoría de Morse. La teoría de Morse discreta ha dado lugar a una importante cantidad de trabajos vinculados al estudio de los complejos simpliciales, posets, teoría de homología y topología computacional, y parece ir convirtiéndose en una herramienta muy útil para muchos campos de aplicación. Las deniciones de función de Morse discreta y de punto crítico de una tal función pueden parecer un tanto extrañas y totalmente desligadas de la denición conocida para variedades diferenciables, pero cobran pleno sentido si se piensa que no son sino una consecuencia de la idea de campo vectorial discreto. Siguiendo el modelo de la teoría de Morse clásica, Forman introduce la noción de campo gradiente discreto sobre un complejo como cadenas formadas por símplices de dimensiones consecutivas, de manera 6 que representen líneas de ujo donde la función sea decreciente, y ademas reejen sucesiones de deformaciones en los símplices que la forman (esencialmente colapsos) que simplican el tipo de homotopía del complejo. Teniendo en cuenta estos principios, es claro que lo adecuado es denir función de Morse discreta asignando un número a cada símplice, de manera que se respete el orden dado por la dimensión, excepto a lo más en una (co)cara del símplice. Así se explica también la denición de símplice crítico de una función de Morse discreta, que no son sino aquellos no incluidos en el campo, es decir, no afectados por las deformaciones codicadas en el mismo, y por tanto aquellos que contienen información topológica relevante. En este trabajo presentaremos las ideas esenciales y los resultados básicos de la teoria de Morse discreta. No se incluyen las demostraciones de aquellos teoremas y proposiciones de mayor complejidad técnica que esten expuestos detalladamente en las referencias citadas, y está organizado en dos Capítulos. En el Capítulo 1, se presentan muy escuetamente las deniciones básicas de complejos simpliciales y celulares, teoría de homotopía y homología simplicial que pueden consultarse en cualquier texto elemental de topología algebraica. Además, se recogen los conceptos mínimos esenciales de la teoría de Morse diferenciable, y se exponen, sin demostración, los que suelen considerarse como resultados fundamentales de la teoria. En el Capítulo 2 se introducen las ideas y deniciones fundamentales de la teoria de Morse discreta: función de Morse, símplice crítico y campo gradiente discreto. Se destaca que la teoría se puede desarrollar en términos de la teoria de grafos, pues la idea central, es decir, el concepto de campo gradiente, se puede interpretar como un tipo especial de emparejamiento en el diagrama de Hasse del complejo. Ello permite a Forman obtener una caracterización sencilla de los campos vectoriales que son gradientes de funciones de Morse. En la última Sección, se tratan las funciones de Morse perfectas sobre 2-complejos, que son aquellas en las que el número de símplices críticos de cada dimensión coincide con el correspondiente número de Betti del complejo. Se da su caracterización en términos del número de colapso, denido en [4], y se dan ejemplos de espacios que no las admiten. Por tanto, se plantea el problema de encontrar aquellas funciones de Morse con el menos número posible de símplices críticos, es decir, las funciones óptimas. Estas funciones son de gran interés, pues cuanto menos puntos críticos tenga una función de Morse, más ecaz será para describir la topologia del complejo. Desgraciadamente, no se conoce un algoritmo general eciente para obtenerlas. Concluímos el trabajo observando que una función de Morse óptima corresponde a un emparejamiento máximo en el diagrama de Hasse del complejo. 7 Capítulo 1 Preliminares 1.1. Nociones básicas de Homotopía y Homología Simplicial En la primera sección se abordarán las nociones básicas de homotopía y homología de espacios topológicos. Aunque los principales teoremas de la Teoría de Morse discreta se han formulado sobre complejos celulares, en este trabajo la desarrollaremos para complejos simpliciales para dar una presentación más clara. Por tanto, empezaremos con el estudio previo de las principales propiedades de estos complejos simpliciales. En este trabajo solo trataremos con complejos simpliciales nitos. Definición 1.1.1 . Sean f y g:X→Y dos aplicaciones continuas entre espacios topológicos. Se dice que f y g son homotópicas si existe una aplicación continua H:X×I→Y tal que H(x, 0) = f(x) y H(x, 1) = g(x) . A H se le llama homotopía enre f y g . Se tiene que la relación de ser homotópicas es una relación de equivalencia en el conjunto de aplicaciones continuas de X a Y , estable por composición de aplicaciones continuas; es decir, si dos aplicaciones son homotópicas, sus composiciones con una aplicación continua también lo son. Definición 1.1.2 . Dos espacios topológicos X e Y se dicen homotópicamente equivalentes , o del mismo tipo de homotopía, si existen aplicaciones continuas f:X→Y , g:Y→X tales que g◦f≃idX y f◦g≃idY , es decir, sus composiciones son homotópicas con la identidad en cada espacio. Si i:A ,→X es la inclusión canónica, se dice que A es retracto de deformación de X si existe una aplicación continua j:X→A tal que j◦i=idA , e i◦j≃idX . Cuando A es un punto, se dice que X es contráctil . Definición 1.1.3 . El conjunto de puntos {a0, a1, . . . , an} ∈ Rm son afínmente independientes si los vectores {a1−a0, . . . , an−a0} son linealmente independientes. Dados a0, a1, . . . , an∈Rm puntos afínmente independientes, se dene el n− símplice generado por 8 a0, a1, . . . , an como el conjunto convexo σn=(x∈Rm/ x = n X i=0 λiai, con λi≥0, n X i=0 λi= 1) Los coecientes λi son llamados las coordenadas baricéntricas . Llamaremos interior de σ a ◦ σ= {x∈σ;λi>0} . Los puntos ai se llamaran vértices de σ y se escribirá σ= (a0, a1, . . . , an) . Así, un 0-símplice es un punto, un 1-símplice es un segmento, un 2-símplice es un triángulo, un 3-símplice es un tetraedro, etc. Sean dos símplices σ y τ en Rm . Se dirá que τ es cara de σ , y lo denotaremos por τ≤σ si los vértices de τ son vértices de σ . Si τ6=σ y τ≤σ diremos que τ es una cara propia de σ y lo escribiremos entonces τ < σ . La unión de caras propias de un n− símplice σ= (a0, a1, . . . , an) se llamará borde de σ , y lo denotaremos por • σ . Nótese que ˙ • σ=x∈σ;x= n P i=0 λiai tal que λj= 0 para algún j , y por tanto, o σ=σ−• σ . Definición 1.1.4 . Llamaremos complejo simplicial a una colección nita K de símplices en algún Rm vericando: Si σ∈K y τ≤σ , entonces τ∈K . Si σ, σ0∈K , y σ∩σ06=∅ entonces σ∩σ0∈K es una cara común de σ y σ0 . 9 El subnivel 2 es del mismo tipo de homotopía que una 0-célula. El subnivel 3 es del mismo tipo de homotopía que el 1 con una 1-célula pegada. El subnivel 4 es homotópicamente equivalente al 3 tras pegarle una 1-célula. El subnivel 5 es homotópicamente equivalente al 4 con una 2-célula pegada. En resumen, M puede obtenerse, salvo tipo de homotopía, pegando células a los conjuntos Ma determinados por los puntos críticos. Este ejemplo ilustra los siguientes teoremas que caracterizan el tipo de homotopía de una variedad compacta en términos de puntos críticos de funciones de Morse, y cuya demostración detallada puede verse en [9] . Teorema 1.2.2 . Sean M una variedad diferenciable compacta, f:M→R una función diferenciable, y a, b ∈R . Si f−1[a, b] = {p∈M /a ≤f(p)≤b} no contiene puntos críticos, entonces Ma es difeomorfo a Mb . Teorema 1.2.3 . Sean M una variedad diferenciable, f:M→R función diferenciable, y p un punto crítico no degenerado de f de índice λ , con f(p) = c . Dado  > 0 , si f−1[c−, c +] no contiene puntos críticos además de p , entonces Mc+ tiene el mismo tipo de homotopía de Mc− con una λ -célula pegada. Como consecuencia de ambos resultados, se obtiene el llamado Teorema fundamental de la teoría de Morse. Teorema 1.2.4 . Sean M una variedad diferenciable compacta y f:M→R función de Morse. Entonces M tiene el tipo de homotopía de un CW-complejo, con una célula de dimensión λ por cada punto crítico de índice λ . 16 Capítulo 2 Teoría de Morse Discreta 2.1. Funciones de Morse discretas Abordaremos ahora el estudio de las funciones de Morse discretas. Se trata de aplicaciones que asignan valores reales a los i− símplices de un complejo, siguiendo una serie de reglas que respetan de manera casi compatible la estructura simplicial. Esencialmente, puede decirse que una función de Morse discreta f es aquella que asigna a toda cara de un símplice σ un valor estrictamente menor que f(σ) con a lo más una excepción y, a todo símplice del que σ es cara un valor estrictamente mayor que f(σ) con a lo más una excepción. De forma más precisa, Forman introduce la siguiente denición, que aunque pueda parecer muy distinta de la noción de función de Morse en el caso diferenciable, es una consecuencia natural de la noción de campo gradiente adaptada al contexto combinatorio. Definición 2.1.1 . Una función de Morse discreta denida sobre K es una función f:K→R , tal que para todo n− símplice σ(n) (i) Si τ(n+1) es un (n+ 1) − símplice de K , se tiene que card nτ(n+1) > σ |f(τ)≤f(σ)o≤1 (ii) Si ν(n−1) es un (n−1) − símplice de K , se tiene que card nν(n−1) < σ |f(ν)≥f(σ)o≤1 En el ejemplo siguiente, la función de la izquierda no es de Morse, mientras que la de la derecha sí lo es. 17 La idea de la denición es que si σ < τ y f(σ)≥f(τ) , la función decrece desde σ hacia τ , por lo que se podrá empujar τ desde la cara σ . En cierto sentido, f indica los símplices que se pueden eliminar sin alterar el tipo de homotopía del complejo. Por tanto, si como en el caso diferenciable se pretende disponer de una noción de elemento crítico de una función de Morse que reeje la información relevante sobre la topologia del complejo, es lógico considerar que dichos elementos críticos correspondan a los símplices que no sufran deformaciones. Esta idea intuitiva es la que está detrás de la siguiente denición. Definición 2.1.2 . Dada una función de Morse discreta f:K→R , diremos que un n− símplice σ∈K es crítico para f si se cumplen las dos condiciones siguientes: (i)card τ(n+1) > σ |f(τ)≤f(σ)= 0 (ii)card ν(n−1) < σ |f(ν)≥f(σ)= 0 De las condiciones (i) e (ii) de la denición anterior, se deduce inmediatamente que σ es un n− símplice no crítico si y sólo si se verica una de las siguientes condiciones: (i0) Existe τ(n+1) > σ tal que f(τ(n+1))≤f(σ) (ii0) Existe ν(n−1) < σ tal que f(ν(n−1))≥f(σ) Éstas dos condiciones no pueden darse simultáneamente en virtud del Lema 2.5 de [5]. Es interesante señalar que no siempre los símplices críticos de una función de Morse discreta indican propiedades topológicas de interés, ya que su número puede ser innecesariamente elevado o corresponder a funciones de Morse, en cierto modo, triviales. Por ejemplo, si K es un complejo cualquiera y f:K→R está dada por f(σ) = dim(σ) , todos los símplices de K serían críticos respecto a f . De hecho, como se 18 estudia en la Sección 2.3, una función de Morse discreta será tanto más adecuada para indicar cómo es la topología de un complejo cuanto menos símplices críticos tenga. Los siguientes resultados prueban que, al igual que en el caso diferenciable, y en condiciones relativamente generales, los valores máximos y mínimos de una función de Morse discreta se alcanzan sobre símplices críticos. Proposición 2.1.3 . Sea f una función de Morse discreta denida sobre un complejo simplicial K. Se verica que todo mínimo de f se alcanza sobre un 0-símplice de K que ademas es vértice crítico de f en K. Demostración. En primer lugar, probemos que todo mínimo de f debe alcanzarse necesariamente sobre un 0-símplice. En efecto, si se alcanzara en un símplice de dimensión p≥1 , éste tiene p+ 1 símplices en su borde y, por tanto, no se cumpliría la segunda condición de la denición de función de Morse discreta. Veamos ahora que los 0-símplices sobre los que se alcanzan los mínimos de f han de ser críticos. Dado que los mínimos se alcanzan sobre símplices de dimensión 0, sólo tiene sentido plantearse para éstos la primera condición de la denición de símplice crítico, y ésta se tiene precisamente por ser mínimos.  Proposición 2.1.4 . Sea f una función de Morse discreta denida sobre un complejo simplicial K tal que ningún símplice de dimension menor que la máxima tiene caras libres. Se verica que todo máximo de f se alcanza sobre un símplice de dimensión máxima de K que es, además, punto crítico de f en K. Demostración. En primer lugar, recordemos que en un complejo simplicial de dimensión n en las condiciones anteriores, todo p− símplice tal que p≤n−1 es cara de al menos dos (p+ 1) -símplices. Sea σ un símplice de dicho complejo sobre el cual f alcanza un máximo y supongamos que su dimensión es p≤n−1 . Sabemos que han de existir al menos dos (p+1) -símplices τ1 y τ2 tales que σ es cara de ambos. Dado que f alcanza un máximo sobre σ , en particular se verica que f(σ)> f(τi) , con i= 1,2 . Esta última armación está en contradicción con la primera condición de la denición de función de Morse discreta. Por tanto, σ ha de ser un símplice de dimensión máxima. Para concluir, probemos que σ es símplice crítico de f . Dado que σ es de dimensión máxima, no existen símplices que lo tengan como cara y por tanto, sólo tiene sentido comprobar la segunda condición de la denición de símplice crítico, pero ésta se verica directamente ya que equivale a armar f alcanza sobre σ un máximo.  19 Como en el caso diferenciable, en la teoría de Morse discreta se dispone de una versión de las desigualdades de Morse, que relacionan los números de Betti y la característica de Euler de un complejo simplicial con la cantidad de símplices críticos de una función de Morse denida sobre él. Si mp(f) denota el número de p -símplices críticos de f , se tienen los siguientes resultados, cuyas demostraciones detalladas pueden verse en 1.7 y 1.8 de [6] o en 4.5.1 y 4.5.3 de [10]: Teorema 2.1.5 . (Desigualdades fuertes de Morse). Sea K un complejo simplicial nito sobre el que esta denida una función de Morse discreta f. Para todo p≥0 se tiene que mp(f)−mp−1(f) + · · · ± m0(f)≥bp−bp−1+· · · ± b0 Donde mp(f) es el número de p− símplices críticos de f . Dicho número se llama número de Morse de f de índice p. Teorema 2.1.6 . (Desigualdades débiles de Morse). Sea K un complejo simplicial nito sobre el que está denida una función de Morse discreta f. Entonces: (i) Para todo p≥0 se tiene que mp(f)≥bp . (ii) m0(f)−m1(f) + m2(f)− · · · ± mdim(K)(f) = b0−b1+b2− · · · ± bdim(K) Obsérvese que de la desigualdad (i) se deduce que los números de Betti establecen una cota inferior al número de símplices críticos de cada dimensión, y por tanto siempre existen 0-símplices críticos para funciones de Morse sobre complejos nitos. También pueden interpretarse las desigualdades de Morse como cotas superiores de los números de Betti de un complejo, aunque desde luego son de escaso interés si el número de símplices es elevado. En ese caso, se presentan dos dicultades: por un lado, no es fácil denir explícitamente funciones de Morse sobre él, y por otro, el número de sus símplices críticos, incluso el de los de dimensión 0, puede ser tan grande que la información proporcionada sea irrelevante. Esta posibilidad refuerza el interés por desarrollar la teoría de Morse discreta sobre CW -complejos, aunque los detalles técnicos resulten más complicados. Definición 2.1.7 . Sea c∈R , f una función de Morse discreta denida sobre un complejo simplicial K , se dene el subcomplejo de nivel c como el subcomplejo de K : K(c) = [ f(σ)≤c[ τ≤σ τ 20 La siguiente gura representa los subcomplejos de nivel de la función de Morse denida en la gura que sigue a la Denición 2.1.1. Los siguientes resultados son análogos a los ya mencionados para la teoría de Morse diferenciable, y una demostración detallada de los mismos pueden verse en 4.3.1, 4.3.3 y 4.3.5 de [2]. Proposición 2.1.8 . Sean f:K→R una función de Morse discreta, y a, b ∈R tales que no hay símplices críticos en f−1(a, b] . Entonces K(b) es homotópicamente equivalente a K(b) . De hecho, K(b) colapsa a K(a) . Proposición 2.1.9 . Sea f:K→R una función de Morse discreta, y a, b ∈R tales que hay un único símplice crítico σp∈f−1(a, b] . Entonces existe una aplicación F:S(p−1) →K(a) , tal que K(b) es homotópicamente equivalente a K(a)∪FBp . Teorema 2.1.10 . (Teorema fundamental de la teoría de Morse discreta) Sea K un complejo simplicial, y f una función de Morse discreta sobre K. Se tiene que K es homotópicamente equivalente a un CW complejo con exactamente una célula de dimensión p por cada símplice crítico de dimensión p. Este resultado es interesante pues signica que mientras menor sea el número de símplices críticos de las funciones de Morse sobre un complejo, más sencilla será la estructura celular que podemos denir sobre él. Ahora bien, salvo en los casos particulares que se indican en la Sección 2.3, no es posible dar un método general eciente para obtener para obtener una función de Morse óptima, ni siquiera en dimensión dos. 21 2.2. Campos Gradientes Discretos En realidad, la noción básica de la teoría de Morse discreta es la de campo gradiente discreto, que está a su vez basada en la noción de campo vectorial en una variedad diferenciable. Suelen éstos representarse grácamente como una sucesión de echas, que corresponden a vectores tangentes a ciertos puntos de una trayectoria en la variedad. Por tanto, parece natural trasladar esta noción a los complejos simpliciales partiendo del concepto de trayectoria en un complejo simplicial, entendida, no solo como una sucesión de vértices y aristas, sino en general, para cualquier dimensión k , como una sucesión o una cadena de símplices k -dimensionales de manera que dos consecutivos comparten una cara k−1 -dimensional. Entonces el papel de las echas en la visualización de un campo vectorial diferenciable lo desempeñarían las echas dibujadas entrando en el k− símplice en el que nos situamos en nuestro recorrido, partiendo de su intersección con el anterior. Pero como ya indicamos en la Introducción, la teoría de Morse discreta se propone simplicar el tipo de homotopía de un complejo llevando a cabo operaciones de eliminación o deformación en algunos símplices, y para codicar este procedimiento se hace lo mismo que para expresar grácamente un colapso elemental; dibujaremos una echa que entre en el símplice que estamos colapsando y que salga de la cara libre a lo largo de la cual estamos haciendo el colapso. Por tanto, en la teoría de Morse discreta juegan un papel esencial los campos vectoriales discretos en los que las echas reejen las operaciones indicadas, y por ello deben cumplir unas restricciones mínimas, como son que de un símplice no puede salir más de una echa, en un símplice no puede entrar más de una echa, y que en un símplice no puede entrar y salir a la vez una echa de él, y estas ideas intuitivas quedan formalizadas en la siguiente: Definición 2.2.1 . Sea K un complejo simplicial. Un campo vectorial discreto sobre K es una colección V de pares de símplices de K de dimensiones consecutivas, V=nα(p), β(p+1)/α(p)< β(p+1)o, tales que cada símplice de K está a lo más en un par de V . En el siguiente dibujo se indica un campo vectorial discreto denido sobre un 2-símplice, donde las echas representan los pares de símplices que lo forman. 22 Sea K un complejo simplicial y V un campo vectorial discreto denido sobre K . Un V− camino es una sucesión de símplices, α(p) 0, β(p+1) 0, α(p) 1, β(p+1) 1, . . . , α(p) r, β(p+1) r, α(p) r+1 tal que para todo i= 0, . . . , r se tiene α(p) i< β(p+1) i , α(p) i, β(p+1) i∈V y β(p+1) i> α(p) i+1 6=α(p) i . Se dirá que un V− camino es cerrado si r≥0 y α0=αr+1 . A continuación se introduce el concepto de campo gradiente asociado a una función de Morse discreta, que consiste en seleccionar las parejas de símplices (σ, τ) con f(τ)< f(σ) . Procediendo de esta forma se puede decir que un campo gradiente es aquel en cuyas trayectorias la función es decreciente. Definición 2.2.2 . Sea K un complejo simplicial sobre el que está denida una función de Morse discreta f . Se dene el campo gradiente asociado a f , Vf , como la colección de pares de símplices de K , α(p), β(p+1) , con α(p)< β(p+1) , tales que α(p), β(p+1)∈Vf si y sólo si f(β)≤f(α) . En la siguiente gura, en el dibujo de la derecha se indica el campo gradiente asociado a la función de Morse f denida sobre el 1-complejo de la izquierda. 23 Se puede comprobar que el campo gradiente inducido por una función de Morse verica la denición de campo vectorial discreto. Proposición 2.2.3 . Todo campo gradiente Vf es un campo vectorial discreto. Nótese que el campo gradiente contiene toda la información relativa a los símplices críticos de la función. En efecto, los símplices críticos de Vf son aquellos que no cumplen ninguna de las condiciones de la Denición 2.1.2. Como es evidente que es más cómodo representar Vf que indicar los valores de f , en la teoría de Morse discreta suele trabajarse con los gradientes de las funciones en vez de con las propias funciones, salvo en las cuestiones relacionadas con los complejos de nivel. Por tanto, un problema interesante desde el punto de vista práctico es cómo poder asegurar que cuando representamos un campo discreto sobre un complejo simplicial es el gradiente de una función de Morse. La denición de campo gradiente permite aclarar las condiciones dadas en la denición de función de Morse discreta. En efecto, la noción básica de la teoría es la de campo vectorial discreto, y en su denición se pretende que queden reejadas las propiedades que ya indicamos. Por tanto, el primer requisito que ha de vericar una denición adecuada de función de Morse discreta es que se adapte bien a la idea geométrica de campo gradiente. Desde este punto de vista, es claro que tal tipo de función debe estar denida sobre los elementos de K , es decir, sobre sus símplices, y tomar valores en R . Por otra parte, si un par de símplices aparece en el gradiente, los valores de la función en ellos deben expresar 24 dos condiciones: por un lado el primer elemento del par es una cara libre del segundo, por el cual se produce un colapso elemental a través de dicho par, y por tanto la función debe ser decreciente al ir recorriendo la trayectoria de dicho gradiente. Todo ello se satisface exigiendo a la función las condiciones de la Denición 2.2.1. Trataremos a continuación el problema de caracterizar los campos vectoriales discretos que son campos gradientes. Veremos que son aquellos en los que no existen V− caminos cerrados de dimensión 1. Comencemos por formalizar el concepto de camino gradiente. Definición 2.2.4 . Sea K un complejo simplicial sobre el que está denida una función de Morse discreta f y sea Vf el campo gradiente asociado a f . Un camino gradiente ó Vf− camino es una sucesión de símplices: α(p) 0, β(p+1) 0, α(p) 1, β(p+1) 1, . . . , α(p) r, β(p+1) r, α(p) r+1, tal que para todo i= 0, . . . , r , el par α(p), β(p+1) , con α(p)< β(p+1) , está en Vf . A partir de esta denición se obtiene el siguiente resultado, que caracteriza los caminos gradientes de una función de Morse como aquellos a lo largo de los cuales es decreciente. Teorema 2.2.5 . Si Vf es el campo gradiente de una función de Morse discreta f denida sobre un complejo simplicial K, una sucesión de símplices α(p) 0, β(p+1) 0, α(p) 1, β(p+1) 1, . . . , α(p) r, β(p+1) r, α(p) r+1 es un Vf -camino si y sólo si α(p) i< β(p+1) i> α(p) i+1 , para cada i= 0, . . . , r y f(α0)≥f(β0)> f(α1)≥f(β1)>· · · ≥ f(βr)> f(αr+1) Demostración. Supongamos que la sucesión de símplices α(p) 0, β(p+1) 0, α(p) 1, β(p+1) 1, . . . , α(p) r, β(p+1) r, α(p) r+1 es un V -camino asociado al campo gradiente V , es decir, es una camino gradiente de f en M . Por denición de V -camino se verica que α(p) i< β(p+1) i> α(p) i+1 con i= 0, . . . , r . Por otro lado, al ser V campo gradiente y dado que (α(p) i< β(p+1) i)∈V , se tiene que f(β(p+1) i)≤f(α(p) i) y f(α(p) i+1)< f(β(p+1) i) 25 a símplices de dimensión p−1 que son caras de σ ) estan orientadas en sentido descendente, es decir, van desde vértices del nivel superior a los de nivel inmediatamente inferior y, por tanto, dichas aristas no modican su orientación al construir Hf(K) .  A la vista de la proposición anterior, puede armarse que los símplices críticos de una función de Morse discreta f denida sobre un complejo simplicial K son aquellos en los que f y el orden inducido en la estructura simplicial de K por la relación ser cara de son compatibles. Corolario 2.2.18 . Bajo las hipótesis de la proposición anterior se verican las siguientes propiedades : (i) σ es un vértice crítico de f en K si y sólo si todas las aristas ei incidentes en vσ cumplen que ∂ei=vσ−vτ . (ii) σ es un símplice crítico de dimensión máxima si y solo si todas las aristas ej incidentes en vσ cumplen que ∂ej=vν−vσ . Demostración. Basta aplicar la proposición anterior y tener en cuenta que en el diagrama de Hasse los vértices correspondientes a símplices de dimensión máxima unicamente están conectados a los del nivel inmediatamente inferior y, por otro lado, los vértices correspondientes a símplices de dimensión mínima sólo estan conectados a los del nivel inmediatamente superior.  2.3. Funciones de Morse óptimas y perfectas. Por las desigualdades débiles de Morse, sabemos que el número de i− símplices críticos de una función de Morse discreta sobre un complejo simplicial es una cota superior del i− ésimo número de Betti del complejo. Resulta entonces que si tenemos una función en las que se cumplen las igualdades, dicha función tendrá el mínimo número posible de símplices críticos, y por la Proposición 2.1.9 nos indicará el mínimo número de células que admite K . Por otro lado, saber que una función de Morse tiene el mínimo número de símplices críticos es también interesante porque simplica el cálculo de la homología del complejo, ya que se demuestra que el complejo de cadenas simpliciales de K es isomorfo al complejo de cadenas generado por los símplices críticos, llamado complejo de Morse. Así pues, merece la pena destacar y estudiar las propiedades de las funciones de Morse para las que las desigualdades de Morse débiles son igualdades. 32 Definición 2.3.1 . Una función de Morse discreta f denida sobre K se dice F− perfecta si mi(f) = bi(K;F),1≤i≤n . Obsérvese que dichas funciones tienen el menor número posible de símplices críticos sobre K . Veremos a continuación que los grafos y las supercies admiten este tipo de funciones. Proposición 2.3.2 . Todo grafo K admite al menos una función F -perfecta. Demostración. Por simplicar, supondremos que K es conexo; si no lo es, se aplica los razonamientos siguientes a cada una de sus componentes. Si T es un árbol maximal de K con vértice raíz v , por el Lema 4.3 de [6] existe una función de Morse discreta f sobre T cuyo único símplice crítico es v . Si extendemos f a todo K deniendo g(e) = m´ax {f(v), f(w)} , donde e es una arista fuera de T cuyos vértices son v y w , es evidente que m0(g)=1 y m1(g) = b1(K, F) .  Corolario 2.3.3 . Si dim K = 2 y K colapsa a un grafo conexo, entonces K admite funciones F - perfectas. En particular toda triangulación de K de una supercie compacta, conexa y con borde admite tales funciones pues colapsa a un subgrafo de su 1-esqueleto. (ver p.52 [7] ). Proposición 2.3.4 . Si K es una triangulación de una supercie compacta cerrada orientable, existe una función de Morse discreta F - perfecta f:K→R . Demostración. Si τ es un triángulo de K , por el Corolario anterior, existe una función F -perfecta g sobre K−τ . Pero si f es la extensión de g a K dada por f(τ) = m´ax {g(σ) ; σ arista de τ} , f es F -perfecta. En efecto, m0(f) = m0(g)=1 , y m2(f)=1 ya que τ es el único triángulo crítico de f . Además, es inmediato comprobar, aplicando la sucesión de Mayer-Vietoris al par (σ, K −σ) , que b1(K;F) = b1(K−σ, F) , luego m1(f) = m1(g) = b1(K, F) .  Ejemplo. Función de Morse F− perfecta sobre una triangulación del toro T2 , donde los vértices y aristas críticos son los señalados en grueso, y el triángulo negro es el único 2-símplice crítico. 33 Observación. Ninguna triangulación K de una supercie cerrada no orientable admite funciones Q -perfectas. En efecto, en caso contrario, como b2(K, Q) = 0 , aplicando la Proposición 2.1.10 se tendría que K es del mismo tipo de homotopía que un grafo, lo cual no es cierto, pues b2(K, Z2) = 1 . Ahora bien, como K−τ colapsa a un grafo G con b1(G, Z2) = b1(K, Z2) , razonando como antes se llega al siguiente resultado. Proposición 2.3.5 . Cualquier triangulación K de una supercie cerrada no orientable admite una función Z2 - perfecta. Observación. Los ejemplos anteriores parecen indicar que el número máximo de símplices críticos de una función de Morse discreta sobre un complejo coinciden con la suma de los números de Betti de K con coecientes en un cuerpo adecuado F , de manera que cada i -símplice crítico está ligado a un generador de Hi(K, F) . Sin embargo ello no es cierto en general, y el ejemplo típico es la triangulación del sombrero bobo indicada en la gura que viene a continuación. Por ser K contráctil se tiene que para cualquier cuerpo F , bi(K, F)=0 si i= 1,2 y b0(K, F)=1 . Luego si K admitiese una función F -perfecta f , se tendria que m0(f) = 1, m1(f) = 0 y m2(f) = 0 . Sin embargo, como veremos más adelante, toda función de Morse sobre el sombrero bobo tiene al menos 3 símplices críticos. 34 Ejemplo. Función de Morse discreta óptima (no perfecta) sobre el sombrero bobo Se plantea así el problema de caracterizar aquellos complejos que admiten funciones F -perfectas. Para el caso de 2-complejos, ello se consigue mediante el concepto de número de colapso de K , denido por [4] . Definición 2.3.6 . Si K es un 2-complejo, se dene el número de colapso de K , y se denota por co(K) , como el mínimo número de 2-símplices τ1, . . . , τco(K) tal que K−τ1, . . . , τco(K) colapsa a un grafo. Ejemplo. Si K es una supercie con borde no vacío, entonces co(K)=0 . Si K es una supercie cerrada, entonces co(K)=1 . Si K es el sombrero bobo, entonces co(K)=1 . Teorema 2.3.7 . Sea K un 2-complejo conexo. Entonces, K admite una función F - perfecta si y sólo si co(K) = b2(K, F) Demostración. Supongamos que K admite una función de Morse discreta F− perfecta f . Por tanto mi(f) = bi(K, F), i = 0,1,2 . Quitando los m2(f) 2-símplices críticos, obtenemos un subcomplejo K0 con b2(K0,F) = 0 . Obsérvese que la restricción de f a K0 es una función de Morse discreta F− perfecta, y, por tanto, se tiene que K0 tiene el mismo tipo de homotopía que un grafo. Consiguientemente K0 colapsa a un 35 grafo, luego co(K)≤b2(K, F) . En el caso de quitar m<m2(f) 2-símplices de K , el subcomplejo resultante K00 satisface que b2(K00,F)≥1 y por tanto no colapsaría a un grafo. A continuación, supongamos que co(K) = b2(K, F) . Sea G el grafo resultante del colapso de K0 al quitarle co(K) triángulos. Tomando una función F− perfecta g en G , ésta se puede extender a una función de Morse discreta F− perfecta f0 en K0 . Finalmente, se extiende f0 a K asignando a cada 2-símplice restante un valor mayor que el resto de valores que tienen sus 1-caras, y se obtendría una función de Morse discreta F− perfecta.  La existencia de ejemplos de 2− complejos en los que no es posible denir funciones de Morse F− perfectas plantea dos problemas; por una parte, averiguar el mínimo número de símplices críticos que debe tener una función de Morse sobre tales complejos, y, por otra, establecer un método general para obtener funciones de Morse que alcancen ese número. Pero éste es un problema computacionalmente complejo, por lo cual sólo cabe esperar proporcionar algoritmos ecientes en ciertos tipos particulares de 2− complejos, como las supercies o las pseudovariedades (ver [8] ). Definición 2.3.8 . Si FM(K) es el conjunto de funciones de Morse discreta sobre K , y f∈ FM(K) . Sea µ(f) = n P i=0 mi(f) . Se dene la característica de Morse-Smale como γ(K) = min {µ(f)/f ∈ FM(K)} Una función de Morse se llama óptima si γ(K) = µ(f) . Nótese que las funciones de Morse discretas perfectas son óptimas, pero no recíprocamente. Estas funciones son de gran ínterés, pues de acuerdo con el Teorema 2.1.10, permiten simplicar la estructura celular del complejo, y por tanto, el cálculo de su homología. Observación. Sobre un complejo K pueden existir mas de una función óptima, incluso satisfaciendo que su número de i− símplices críticos coincide. Ahora bien, el campo inducido por todos ellos tiene el mismo número de símplices críticos. Entonces, por abuso de lenguaje, diremos que una función de Morse es óptima si su campo asociado tiene el menor número posible de símplices críticos. Es obvio, por las desigualdades de Morse que si f es de Morse, entonces m0(f)≥1 . Pero no es evidente que si f es óptima, m0(f) deba ser 1, pues el exceso de vértices críticos pudiera compensarse con un menor número de símplices críticos de dimensión superior. Pero, en efecto, como cabría esperar, se tiene el siguiente resultado. 36 Proposición 2.3.9 . Si φ:K→R es función de Morse discreta óptima, siendo K un 2-complejo simplicial conexo, entonces m0(φ)=1 . Demostración. Veamos, en primer lugar que sobre todo 2-complejo es posible construir una función de Morse discreta tal que m0(g) = 1, m1(g) = b1(K, F) y para la cual todos los triángulos de K son críticos. En efecto, si g es una función F− perfecta sobre el 1-esqueleto de K , para todo 2-símplice τ∈K , se dene f(τ) = m´ax {g(σ); σ es arista de τ} . Supongamos ahora que φ es óptima sobre K . Entonces tendríamos: (i)m0(φ) + m1(φ) + m2(φ)≤1 + m1(f) + m2(f) = 1 + b1(K) + m2(f) Pero por las desigualdades de Morse, se cumple m0(φ)−m1(φ) + m2(φ) = χ(K)=1−b1(K, F) + m2(f) Es decir, se verica (ii)−m0(φ) + m1(φ)−m2(φ) = −1 + b1(K, F)−m2(f) Luego sumando (i) y (ii) , se llega a 2mi(φ)≤2bi(K, F) , y de nuevo por las desigualdades de Morse, se tendria m1(φ) = b1(K, F) . Por tanto m0(φ) = m2(φ) = 1 + b2(K) , pero como m2(φ)≥b2(K, F) , ha de ser m0(φ)≤1 ; es decir, m0(φ)=1  Teorema 2.3.10 . Una función de Morse discreta φ:K→R es óptima si y solo si mi(φ)≤mi(f) para cualquier función de Morse discreta f. Demostración. Por la proposición anterior, m0(φ)=1=b0(K)≤m0(f) . Además, m1(φ) = b1(K, F)≤m1(K) , y de nuevo por las desigualdades de Morse, tendríamos m2(f) = m1(f) + m0(f)−χ(K)≥m1(φ)+1−χ(K) = m2(φ)  El siguiente resultado caracteriza a los complejos que admiten funciones óptimas con un solo símplice crítico: Proposición 2.3.11 . K es colapsible si y solo si γ(K)=1 , es decir, si admite una función óptima con un solo símplice crítico. 37 Demostración. Si K es colapsible a un vértice v , aplicando 4.3 de [6] , hay una función de Morse discreta denida sobre K tal que v es el único símplice crítico. Recíprocamente, dada una función de Morse discreta f en K con un solo símplice crítico, por las desigualdades de Morse se tiene que m0(f) = 1 . Si v es el único vértice crítico de f en K , entonces a=f(v) es el mínimo valor de f en K . Para  sucientemente pequeño, se tiene que K(a+) = K(a) . Sea b el máximo de f en K . Entonces, K(b) = K , y como el intervalo [a+, b] no contiene ningún valor crítico, aplicando la Proposición 2.18 se tiene que K(b)&K(a) , y, por tanto, K es colapsible.  Este resultado permite comprobar que si K es el sombrero bobo y f es óptima sobre K , entonces m0(f) = m1(f) = m2(f) = 1 . En efecto como m0(f) = 1 y K es contractible, por las desigualdades de Morse se tiene que 1−m1(f)+ m2(f)=1 . Luego m1(f) = m2(f) . Ahora bien, como K no es colapsible, por la proposición anterior m1(f)≥1 por tanto γ(K)≥3 , y en la gura se indica una función de Morse sobre K con γ(K) = 3 . Teniendo en cuenta que la teoría de Morse puede interpretarse en términos de ciertos emparejamietos en un diagramas de Hasse, veremos cómo es posible expresar la idea de función óptima de una forma mucho más visual e intuitiva. Definición 2.3.12 . Sea E un emparejamiento denido sobre un grafo G . Se dirá que E es un emparejamiento máximo si no existe ningún otro emparejamiento denido sobre G que tenga mas aristas que E . Observación. El estudio de las funciones de Morse óptimas sobre un complejo se puede abordar desde el punto de vista de la teoría de emparejamientos. Para ello, basta tener en cuenta la relación que existe etnre el cardinal de un emparejamiento acíclico en Hf(K) y el número de símplices críticos de una función de Morse discreta, ya que por el Teorema 2.2.16, cada símplice crítico corresponde a un vértice no contenido en ninguna arista de dicho emparejamiento. Por tanto, el problema de obtener una función de Morse óptima es equivalente a encontrar un emparejamiento máximo en Hf(K) , en el sentido de que no exista otro con más aristas que él. 38 Referencias bibliográcas 1. Ayala R, Fernández-Ternero D, Vilches JA. (2012).Perfect discrete Morse functions on 2-complexes, Pattern Recogn. Lett. 33:14951500. 2. Capitelli NA. (2009). Colapsabilidad en Variedades Combinatorias y Espacios de Deformaciones. Tesis de Licenciatura, UBA. 3. Chari MK. (2000) On discrete Morse functions and combinatorial decompositions. Discrete Mathematics 217:101-113. 4. Egeioglu Ö, Gonzalez T. (1996) A computationally intractable problem on simplicial complexes. Comput. Geom. 6:8598 5. Forman R. (1998) Morse theory for cell complexes. Advances in Mathematics 134: 90-135. 6. Forman R. (2002) A user's guide to discrete Morse theory. Sém. Lothar. Combin. 48Art. B48, 35p. 7. Glaser LC. (1970) Geometrical combinatorial topology I. Van Nostrand. 8. Lewiner T, Lopes H, Tavares G. (2003).Optimal discrete Morse functions for 2-manifolds. Comput. Geom. 26 (3):221233 9. Milnor J. (1963) Morse theory.Princeton University Press. 10. Sirolli NM. (2007).Teoría de Morse discreta. Tesis de Licenciatura, UBA. 11. Vilches Alarcón, JA. (2003). Funciones de Morse discretas sobre complejos innitos. Tesis Doctoral, Universidad de Sevilla. 39