<p>This thesis is concerned with a structure called the Reeb graph. There are three main problems considered. The first is devising an efficient algorithm for comnstructing the Reeb graph of a simplicial complex with respect to a generic simplex-wise linear real-valued function. We present an algorithm that builds the Reeb graph in almost optimal worst-case deterministic time. This was the first deterministic algorithm with the time bound which is linear up to a logarithmic factor. Without loss of generality, the complex is assumed to be 2-dimensional. The algorithm works by sweeping the function values and maintaining a spanning forest for the preimage, or the level-set, of the value. Using the observation that the operations that change the level-sets are off-line, we was able to achieve the above bound.</p><p>The second topic is the dynamic Reeb graphs. As the function changes its values, the Reeb graph also changes. We are interested in updating the Reeb graph. We reduce this problem to a graph problem that we call retroactive graph connectivity. We obtain algorithms for dynamic Reeb graphs, by using data structures that solve the graph problem. </p><p>The third topic is an argument regarding the complexity of computing Betti numbers. This problem is also related to the Reeb graph by means of the vertical Homology classes. The problem considered here is whether the realization of a simplicial complex in the Euclidean 4-space can result in an algorithm for computing its Homology groups faster than the usual matrix reduction methods. Using the observation that the vertical Betti numbers can always be computed more efficiently using the Reeb graph, we show that the answer to this question is in general negative. For instance, given a square matrix over the field with two elements, we construct a simplicial complex in linear time, realized in euclidean 4-space and a function on it, such that its Horizontal homology group, over the same field, is isomorphic with the null-space of the matrix. It follows that the Betti number computation for complexes realized in the 4-space is as hard as computing the rank for a sparse matrix.</p> / Dissertation

In this thesis, we consider semi-algebraic sets over a real closed field R defined by quadratic polynomials. Semi-algebraic sets of R^k are defined as the smallest family of sets in R^k that contains the algebraic sets as well as the sets defined by polynomial inequalities, and which is also closed under the boolean operations (complementation, finite unions and finite intersections). We prove new bounds on the topological complexity of semi-algebraic sets over a real closed field R defined by quadratic polynomials, in terms of the parameters of the system of polynomials defining them, which improve the known results. We conclude the thesis with presenting two new algorithms along with their implementations.

Let e > 3 and mo,... ,me_i be positive integers with gcd(m0,... ,me_i) = 1, which form an almost arithmetic sequence, i.e., some e - 1 of these form an arithmetic progression. We further assume that m0,... ,mc_1 generate F := Σ e-1 I=0 Nmi minimally. Note that any three integers and also any arithmetic progression form an almost arithmetic sequence. We assume that 0 < m0 < • • • < me-2 form an arithmetic progression and n := mc-i is arbitrary Put p := e - 2. Let K be a field and XQ) ... ,Xj>, Y,T be indeterminates. Let p denote the kernel of the if-algebra homomorphism η: K[XQ, ..., XV) Y) -* K^T], defined by r){Xi) = Tm\.. .η{Xp) = Tmp, η](Y) = Tn. Then, p is the defining ideal for the affine monomial curve C in A^, defined parametrically by Xo = Trr^)...)Xv = T^}Y = T*. Furthermore, p is a homogeneous ideal with respect to the gradation on K[X0)... ,XP,F], given by wt(Z0) = mo, • • •, wt(Xp) = mp, wt(Y) = n. Let 4 := K[XQ> ...,XP) Y)/p denote the coordinate ring of C. With the assumption ch(K) = 0, in Chapter 1 we have derived an explicit formula for μ(DerK(A)), the minimal number of generators for the A-module DerK(A), the derivation module of A. Furthermore, since type(A) = μ(DerK(A)) — 1 and the last Betti number of A is equal to type(A), we therefore obtain an explicit formula for the last Betti number of A as well A minimal set of binomial generatorsG for the ideal p had been explicitly constructed by PatiL In Chapter 2, we show that the set G is a Grobner basis with respect to grevlex monomial ordering on K[X0)..., Xp, Y]. As an application of this observation, in Chapter 3 we obtain an explicit minimal free resolution for affine monomial curves in A4K defined by four coprime positive integers mo,.. m3, which form a minimal arithmetic progression. (Please refer the pdf file forformulas)

CoordenaÃÃo de AperfeiÃoamento de Pessoal de NÃvel Superior / Consideramos o problema de representaÃÃo de superfÃcies imersas em grupos de Lie tridimensionais.Especificamente, nos espaÃos HiperbÃlico, de Sitter, Heisenberg (Riemanniano e pseudo-Riemanniano), nas esferas de Berger e em espaÃos Anti de Sitter exÃticos. Estabelecemos como condiÃÃes de integrabilidade para a existÃncia de uma imersÃo conforme de uma superfÃcie de Riemann nos espaÃos HiperbÃlico, de Sitter, Heisenberg(Riemannianoe pseudo-Riemanniano) as equaÃÃes de compatibilidade para um sistema deprimeira ordem,envolvendo uma equaÃÃo de Dirac com potenciais geomÃtricos. Nas esferas de Berger e nos espaÃos Anti de Sitter exÃticos,demonstra-se que a harmonicidade de uma dada aplicaÃÃo, definida na superfÃcie com valores em abertos da esfera,Ã condiÃÃo suficiente para a existÃncia de uma imersÃo conforme mÃnima. / We considered the problem of representation of immersed surfaces in three-dimensional Lie groups. We search for integrability conditions assuring the existence of a conformal immersion of a given Riemann surface in some Lie group with left-invariant metric. Such compatibility conditions are found to be a first order system, consisting of a Dirac equation with geometric potentials and an extra pair of equations relating the metric and the Hopf differential. In many cases, we proved that the harmonicity of a map, defined in an open of the sphere is a sufficient condition for the existence of a conformal minimal or constant mean curvature immersion.

Le sujet de cette thèse est l'étude d'idéaux monomiaux de l'anneau de polynômes S qui ont une résolution linéaire. D'après un résultat remarquable de Bayer et Stilman et en utilisant la polarisation, la classification des idéaux monomiaux ayant une résolution linéaire est équivalente à la classification des idéaux monomiaux libres de carrés ayant une résolution linéaire. Pour cette raison dans cette thèse nous considérons seulement le cas d'idéaux monomiaux libres de carrés. De plus, le théorème de Eagon-Reiner établit une dualité entre les idéaux monomiaux libres de carrés ayant une résolution linéaire et les idéaux monomiaux libres de carrés Cohen-Macaulay, ce qui montre que le problème de classification des idéaux monomiaux libres de carrés ayant une résolution linéaire est très difficile. Nous rappelons que les idéaux monomiaux libres de carrés sont en correspondance biunivoque avec les complexes simpliciaux d'une part, et d'autre part avec les clutters. Ces correspondances nous motivent pour utiliser les propriétés combinatoires des complexes simpliciaux et des clutters pour obtenir des résultats algébriques. La classification des idéaux monomiaux libres de carrés ayant une résolution linéaire engendrés en degré 2 a été faite par Froberg en 1990. Froberg a observé que l'idéal des circuits d'un graphe G a une résolution 2-linéaire si et seulement si G est un graphe de cordes, i.e. il n'a pas de cycles minimaux de longueur plus grande que 4. Dans [Em, ThVt, VtV, W] les auteurs ont partiellement généralisé les résultats de Froberg à des idéaux engendrés en degré >2. Ils ont introduit plusieurs définitions de clutters de cordes et démontré que les idéaux de circuits correspondant ont une résolution linéaire. Nous pouvons voir les cycles du point de vue topologique, comme la triangulation d'une courbe fermée, dans cette thèse nous utiliserons cette idée pour étudier des clutters associés à des triangulation de pseudo-manifolds en vue d'obtenir une généralisation partielle des résultats de Froberg à des idéaux engendrés en degré >2. Nous comparons notre travail à ceux de [Em, ThVt, VtV, W]. Nous présentons nos résultats dans le chapitres 4 et 5. / In this thesis, we study square-free monomial ideals of the polynomial ring S which have a linear resolution. By remarkable result of Bayer and Stilman [BS] and the technique of polarization, classification of ideals with linear resolution is equivalent to classification of square-free monomial ideals with linear resolution. For this reason, we consider only square-free monomial ideals in S. However, classification of square-free monomial ideals with linear resolution seems to be so difficult because by Eagon-Reiner Theorem [ER], this is equivalent to classification of Cohen-Macaulay ideals. It is worth to note that, square-free monomial ideals in S are in one-to-one correspondence to Stanley-Reisener ideals of simplicial complexes on one hand and the circuit ideal of clutters from another hand. This correspondence motivated mathematicians to use the combinatorial and geometrical properties of these objects in order to get the desired algebraic results. Classification of square-free monomial ideals with 2-linear resolution, was successfully done by Froberg [Fr] in 1990. Froberg observed that the circuit ideal of a graph G has a 2-linear resolution if and only if G is chordal, that is, G does not have an induced cycle of length > 3. In [Em, ThVt, VtV, W] the authors have partially generalized the Fr¨oberg's theorem for degree greater than 2. They have introduced several definitions of chordal clutters and proved that, their corresponding circuit ideals have linear resolutions. Viewing cycles as geometrical objects (triangulation of closed curves), in this thesis we try to generalize the concept of cycles to triangulation of pseudo-manifolds and get a partial generalization of Froberg's theorem for higher dimensional hypergraphs. All the results in Chapters 4 and 5 and some results in Chapter 3 are devoted to be the original results.

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / This dissertation aims at a detailed study of the Hilbert function and graded Betti number and the statements of some theorems that relate these two theories. We will also a brief overview on free resolutions and minimal simplicial complex to demonstrate the theorem of Bayer, Sturmfels and Peeva and then, we will conclude with the following result: given an ideal J we will display a set X P2 such that the minimal resolution the ideal of de nition of X has the same Betti diagram of the minimal resolution of J. / Esta disserta¸c˜ao tem como objetivo um estudo detalhado da fun¸c˜ao de Hilbert e do n´umero graduado de Betti e as demonstra¸c˜oes de alguns teoremas que relacionam essas duas teorias. Faremos tamb´em um breve apanhado sobre resolu¸c˜oes livres minimais e complexo simplicial para demonstrar o teorema de Bayer, Peeva e Sturmfels e por fim e n˜ao menos importante concluiremos com o seguinte resultado: dado um ideal J exibiremos um conjunto X P2 tal que a resolu¸c˜ao minimal do ideal de defini¸c˜ao de X tenha o mesmo diagrama de Betti da resolu¸c˜ao minimal de J.

If <i>E</i> is an exterior algebra on a finite dimensional vector space and <i>M</i> is a graded <i>E</i>-module, the relationship between the resonance varieties of <i>M</i> and the minimal free resolution of <i>M </i>is studied. In the context of Orlik–Solomon algebras, we give a condition under which elements of the second resonance variety can be obtained. We show that the resonance varieties of a general <i>M</i> are invariant under taking syzygy modules up to a shift. As corollary, it is shown that certain points in the resonance varieties of <i>M</i> can be determined from minimal syzygies of a special form, and we define syzygetic resonance varieties to be the subvarieties consisting of such points. The (depth one) syzygetic resonance varieties of a square-free module <i>M</i> over <i>E</i> are shown to be subspace arrangements whose components correspond to graded shifts in the minimal free resolution of <i>_SM</i>, the square-free module over a commutative polynomial ring <i>S </i>corresponding to <i>M</i>. Using this, a lower bound for the graded Betti numbers of the square-free module<i> M</i> is given. As another application, it is shown that the minimality of certain syzygies of Orlik–Solomon algebras yield linear subspaces of their (syzygetic) resonance varieties and lower bounds for their graded Betti numbers.

<p>This dissertation establishes limit theory for topological functionals of geometric complexes from a stochastic process viewpoint. Standard filtrations of geometric complexes, such as the Čech and Vietoris-Rips complexes, have a natural parameter <i>r </i>which governs the formation of simplices: this is the basis for persistent homology. However, the parameter <i>r</i> may also be considered the time parameter of an appropriate stochastic process which summarizes the evolution of the filtration.</p><p>Here we examine the stochastic behavior of two of the foremost classes of topological functionals of such filtrations: the Betti numbers and the Euler characteristic. There are also two distinct setups in which the points underlying the complexes are generated, where the points are distributed randomly in <i>R^d</i> according to a general density (the traditional setup) and where the points lie in the tail of a heavy-tailed or exponentially-decaying “noise” distribution (the extreme-value theory (EVT) setup).<br></p><p>These results constitute some of the first results combining topological data analysis (TDA) and stochastic process theory. The first collection of results establishes stochastic process limits for Betti numbers of Čech complexes of Poisson and binomial point processes for two specific regimes in the traditional setup: the sparse regime—when the parameter <i>r </i>governing the formation of simplices causes the Betti numbers to concentrate on components of the lowest order; and the critical regime—when the parameter <i>r</i> is of the order <i>n^-1/d</i> and the geometric complex becomes highly connected with topological holes of every dimension. The second collection of results establishes a functional strong law of large numbers and a functional central limit theorem for the Euler characteristic of a random geometric complex for the critical regime in the traditional setup. The final collection of results establishes functional strong laws of large numbers for geometric complexes in the EVT setup for the two classes of “noise” densities mentioned above.<br></p>

<p>This dissertation establishes a variety of limit theorems pertaining to rare events in stochastic topology, exploiting probabilistic methods to study simplicial complex models. We focus on the filtration of \vc ech complexes and examine the asymptotic behavior of two topological functionals: the Betti numbers and critical faces. The filtration involves a parameter rn>0 that determines the growth rate of underlying Cech complexes. If rn depends also on the time parameter t, the obtained limit theorems will be established in a functional sense.</p> <p>The first part of this dissertation is devoted to investigating the layered structure of topological complexity in the tail of a probability distribution. We establish the functional strong law of large numbers for Betti numbers, a basic quantifier of algebraic topology, of a geometric complex outside an open ball of radius Rn, such that Rn to infinity as the sample size n increases. The nature of the obtained law of large numbers is determined by the decay rate of a probability density. It especially depends on whether the tail of a density decays at a regularly varying rate or an exponentially decaying rate. The nature of the limit theorem depends also on how rapidly Rn diverges. In particular, if Rn diverges sufficiently slowly, the limiting function in the law of large numbers is crucially affected by the emergence of arbitrarily large connected components supporting topological cycles in the limit.</p> <p>The second part of this dissertation investigates convergence of point processes associated with critical faces for a Cech filtration built over a homogeneous Poisson point process in the d-dimensional flat torus. The convergence of our point process is established in terms of the  Mo-topology, when the connecting radius of a Cech complex decays to 0, so slowly that critical faces are even less likely to occur than those in the regime of threshold for homological connectivity. We also obtain a series of limit theorems for positive and negative critical faces, all of which are considerably analogous to those for critical faces.</p>

In dieser Arbeit studieren wir Lorentz-Mannigfaltigkeiten mit spezieller Holonomie, d.h. ihre Holonomiedarstellung wirkt schwach-irreduzibel aber nicht irreduzibel. Aufgrund der schwachen Irreduzibilität lässt die Darstellung einen ausgearteten Unterraum invariant und damit also auch eine lichtartige Linie. Geometrisch hat dies zur Folge, dass wir zwei parallele Unterbündel (die Linie und ihr orthogonales Komplement) des Tangentialbündels erhalten. Diese Arbeit nutzt diese und weitere Objekte um zu beweisen, dass kompakte Lorentzmannigfaltigkeiten mit Abelscher Holonomie geodätisch vollständig sind. Zudem werden Lorentzmannigfaltigkeiten mit spezieller Holonomie und nicht-negativer Ricci-Krümung auf den Blättern der Blätterung, induziert durch das orthogonale Komplement der parellelen Linie, und maximaler erster Bettizahl untersucht. Schließlich werden vollständige Ricci-flache Lorentzmannigfaltigkeiten mit vorgegebener voller Holonomie konstruiert. / In the present thesis we study dimensional Lorentzian manifolds with special holonomy, i.e. such that their holonomy representation acts indecomposably but non-irreducibly. Being indecomposable, their holonomy group leaves invariant a degenerate subspace and thus a light-like line. Geometrically, this means that, since being holonomy invariant, this line gives rise to parallel subbundles of the tangent bundle. The thesis uses these and other objects to prove that Lorentian manifolds with Abelian holonomy are geodesically complete. Moreover, we study Lorentzian manifolds with special holonomy and non-negative Ricci curvature on the leaves of the foliation induced by the orthogonal complement of the parallel light-like line whose first Betti number is maximal. Finally, we provide examples of geodesically complete and Ricci-flat Lorentzian manifolds with special holonomy and prescribed full holonomy group.