This thesis concerns the relationship between bounded and controlled topology and in particular how these can be used to recognise which homotopy equivalences of reasonable topological spaces are homotopic to homeomorphisms. Let f : X → Y be a simplicial map of finite-dimensional locally finite simplicial complexes. Our first result is that f has contractible point inverses if and only if it is an ε- controlled homotopy equivalences for all ε > 0, if and only if f × id : X × R → Y × R is a homotopy equivalence bounded over the open cone O(Y +) of Pedersen and Weibel. The most difficult part, the passage from contractible point inverses to bounded over O(Y +) is proven using a new construction for a finite dimensional locally finite simplicial complex X, which we call the fundamental ε-subdivision cellulation X'ε. This whole approach can be generalised to algebra using geometric categories. In the second part of the thesis we again work over a finite-dimensional locally finite simplicial complex X, and use the X-controlled categories A*(X), A*(X) of Ranicki and Weiss (1990) together with the bounded categories CM(A) of Pedersen and Weibel (1989). Analogous to the barycentric subdivision of a simplicial complex, we define the algebraic barycentric subdivision of a chain complex over that simplicial complex. The main theorem of the thesis is then that a chain complex C is chain contractible in ( A*(X) A*(X) if and only if “C ¤ Z” 2 (A*(X × R) A*(X × R) is boundedly chain contractible when measured in O(X+) for a functor “ − Z” defined appropriately using algebraic subdivision. In the process we prove a squeezing result: a chain complex with a sufficiently small chain contraction has arbitrarily small chain contractions. The last part of the thesis draws some consequences for recognising homology manifolds in the homotopy types of Poincare Duality spaces. Squeezing tells us that a PL Poincare duality space with sufficiently controlled Poincare duality is necessarily a homology manifold and the main theorem tells us that a PL Poincare duality space X is a homology manifold if and only if X × R has bounded Poincare duality when measured in the open cone O(X+).

The central topic of this thesis is Schnyder's Theorem. Schnyder's Theorem provides a characterization of planar graphs in terms of their poset dimension, as follows: a graph G is planar if and only if the dimension of the incidence poset of G is at most three. One of the implications of the theorem is proved by giving an explicit mapping of the vertices to R^2 that defines a straightline embedding of the graph. The other implication is proved by introducing the concept of normal labelling. Normal labellings of plane triangulations can be used to obtain a realizer of the incidence poset. We present an exposition of Schnyder’s theorem with his original proof, using normal labellings. An alternate proof of Schnyder’s Theorem is also presented. This alternate proof does not use normal labellings, instead we use some structural properties of a realizer of the incidence poset to deduce the result. Some applications and a generalization of one implication of Schnyder’s Theorem are also presented in this work. Normal labellings of plane triangulations can be used to obtain a barycentric embedding of a plane triangulation, and they also induce a partition of the edge set of a plane triangulation into edge disjoint trees. These two applications of Schnyder’s Theorem and a third one, relating realizers of the incidence poset and canonical orderings to obtain a compact drawing of a graph, are also presented. A generalization, to abstract simplicial complexes, of one of the implications of Schnyder’s Theorem was proved by Ossona de Mendez. This generalization is also presented in this work. The concept of order labelling is also introduced and we show some similarities of the order labelling and the normal labelling. Finally, we conclude this work by showing the source code of some implementations done in Sage.

The central topic of this thesis is Schnyder's Theorem. Schnyder's Theorem provides a characterization of planar graphs in terms of their poset dimension, as follows: a graph G is planar if and only if the dimension of the incidence poset of G is at most three. One of the implications of the theorem is proved by giving an explicit mapping of the vertices to R^2 that defines a straightline embedding of the graph. The other implication is proved by introducing the concept of normal labelling. Normal labellings of plane triangulations can be used to obtain a realizer of the incidence poset. We present an exposition of Schnyder’s theorem with his original proof, using normal labellings. An alternate proof of Schnyder’s Theorem is also presented. This alternate proof does not use normal labellings, instead we use some structural properties of a realizer of the incidence poset to deduce the result. Some applications and a generalization of one implication of Schnyder’s Theorem are also presented in this work. Normal labellings of plane triangulations can be used to obtain a barycentric embedding of a plane triangulation, and they also induce a partition of the edge set of a plane triangulation into edge disjoint trees. These two applications of Schnyder’s Theorem and a third one, relating realizers of the incidence poset and canonical orderings to obtain a compact drawing of a graph, are also presented. A generalization, to abstract simplicial complexes, of one of the implications of Schnyder’s Theorem was proved by Ossona de Mendez. This generalization is also presented in this work. The concept of order labelling is also introduced and we show some similarities of the order labelling and the normal labelling. Finally, we conclude this work by showing the source code of some implementations done in Sage.

Splines are piecewise polynomial functions of a given order of smoothness r on a triangulated region (or polyhedrally subdivided region) of Rd. The set of splines of degree at most k forms a vector space Crk() Moreover, a nice way to study Cr k()is to embed n Rd+1, and form the cone b of with the origin. It turns out that the set of splines on b is a graded module Cr b() over the polynomial ring R[x1; : : : ; xd+1], and the dimension of Cr k() is the dimension o This dissertation follows the works of Billera and Rose, as well as Schenck and Stillman, who each approached the study of splines from the viewpoint of homological and commutative algebra. They both defined chain complexes of modules such that Cr(b) appeared as the top homology module. First, we analyze the effects of gluing planar simplicial complexes. Suppose 1, 2, and = 1 [ 2 are all planar simplicial complexes which triangulate pseudomanifolds. When 1 \ 2 is also a planar simplicial complex, we use the Mayer-Vietoris sequence to obtain a natural relationship between the spline modules Cr(b), Cr (c1), Cr(c2), and Cr( \ 1 \ 2). Next, given a simplicial complex , we study splines which also vanish on the boundary of. The set of all such splines is denoted by Cr(b). In this case, we will discover a formula relating the Hilbert polynomials of Cr(cb) and Cr (b). Finally, we consider splines which are defined on a polygonally subdivided region of the plane. By adding only edges to to form a simplicial subdivision , we will be able to find bounds for the dimensions of the vector spaces Cr k() for k 0. In particular, these bounds will be given in terms of the dimensions of the vector spaces Cr k() and geometrical data of both and . This dissertation concludes with some thoughts on future research questions and an appendix describing the Macaulay2 package SplineCode, which allows the study of the Hilbert polynomials of the spline modules.

<p>In this dissertation we study combinatorial Hodge Laplacians on simplicial com-</p><p>plexes using tools generalized from spectral graph theory. Specifically, we consider</p><p>generalizations of graph Cheeger numbers and graph random walks. The results in</p><p>this dissertation can be thought of as the beginnings of a new spectral theory for</p><p>simplicial complexes and a new theory of high-dimensional expansion.</p><p>We first consider new high-dimensional isoperimetric constants. A new Cheeger-</p><p>type inequality is proved, under certain conditions, between an isoperimetric constant</p><p>and the smallest eigenvalue of the Laplacian in codimension 0. The proof is similar</p><p>to the proof of the Cheeger inequality for graphs. Furthermore, a negative result is</p><p>proved, using the new Cheeger-type inequality and special examples, showing that</p><p>certain Cheeger-type inequalities cannot hold in codimension 1.</p><p>Second, we consider new random walks with killing on the set of oriented sim-</p><p>plexes of a certain dimension. We show that there is a systematic way of relating</p><p>these walks to combinatorial Laplacians such that a certain notion of mixing time</p><p>is bounded by a spectral gap and such that distributions that are stationary in a</p><p>certain sense relate to the harmonics of the Laplacian. In addition, we consider the</p><p>possibility of using these new random walks for semi-supervised learning. An algo-</p><p>rithm is devised which generalizes a classic label-propagation algorithm on graphs to</p><p>simplicial complexes. This new algorithm applies to a new semi-supervised learning</p><p>problem, one in which the underlying structure to be learned is flow-like.</p> / Dissertation

La théorie de l'homologie généralise en dimensions supérieures la notion de connectivité dans les graphes. Étant donné un domaine, décrit par un complexe simplicial, elle définit une famille de groupes qui capturent le nombre de composantes connexes, le nombre de trous, le nombre de cavités et le nombre de motifs équivalents en dimensions supérieures. En pratique, l'homologie permet d'analyser des systèmes de données complexes, interprétés comme des nuages de points dans des espaces métriques. La théorie de l'homologie persistante introduit une notion robuste d'homologie pour l'inférence topologique. Son champ d'application est vaste, et comprend notamment la description d'espaces des configurations de systèmes dynamiques complexes, la classification de formes soumises à des déformations et l'apprentissage en imagerie médicale. Dans cette thèse, nous étudions les ramifications algorithmiques de l'homologie persistante. En premier lieu, nous introduisons l'arbre des simplexes, une structure de données efficace pour construire et manipuler des complexes simpliciaux de grandes dimensions. Nous présentons ensuite une implémentation rapide de l'algorithme de cohomologie persistante à l'aide d'une matrice d'annotations compressée. Nous raffinons également l'inférence de topologie en décrivant une notion de torsion en homologie persistante, et nous introduisons la méthode de reconstruction modulaire pour son calcul. Enfin, nous présentons un algorithme de calcul de l'homologie persistante zigzag, qui est une généralisation algébrique de la persistance. Pour cet algorithme, nous introduisons de nouveaux théorèmes de transformations locales en théorie des représentations de carquois, appelés principes du diamant. Ces algorithmes sont tous implémentés dans la librairie de calcul Gudhi. / The theory of homology generalizes the notion of connectivity in graphs to higher dimensions. It defines a family of groups on a domain, described discretely by a simplicial complex that captures the connected components, the holes, the cavities and higher-dimensional equivalents. In practice, the generality and flexibility of homology allows the analysis of complex data, interpreted as point clouds in metric spaces. The theory of persistent homology introduces a robust notion of homology for topology inference. Its applications are various and range from the description of high dimensional configuration spaces of complex dynamical systems, classification of shapes under deformations and learning in medical imaging. In this thesis, we explore the algorithmic ramifications of persistent homology. We first introduce the simplex tree, an efficient data structure to construct and maintain high dimensional simplicial complexes. We then present a fast implementation of persistent cohomology via the compressed annotation matrix data structure. We also refine the computation of persistence by describing ideas of homological torsion in this framework, and introduce the modular reconstruction method for computation. Finally, we present an algorithm to compute zigzag persistent homology, an algebraic generalization of persistence. To do so, we introduce new local transformation theorems in quiver representation theory, called diamond principles. All algorithms are implemented in the computational library Gudhi.

The topic of this thesis are subdivisions of simplicial complexes, in particular we focus on the so-called antiprism triangulation. In the first main part, the real-rootedness of the h-polynomial of the antiprism triangulation of the simplex is proven. Furthermore, we study combinatorial interpretations of several invariants as the h- and local h-vector. In the second part, we show the almost strong Lefschetz property of the antiprism triangulation for every shellable simplicial complex.

Simplicial complexes are mathematical objects whose importance stretches from topology to commutative algebra and combinatorics. In this thesis we focus on the family of balanced simplicial complexes. A d-dimensional simplicial complex is balanced if its 1-skeleton can be properly (d+1)-colored, as in the classical graph theoretic sense. Equivalently, a d-dimensional complex is balanced iff it admits a non-degenerate simplicial projection to the d-simplex. We present results on these complexes from a number of different points of view. After two introductory chapters, we exhibit in chapter 3 an infinite family of balanced counterexamples to Stanley's partitionability conjecture. These complexes, which are in addition constructible, answer a question of Duval et al. in the negative. Next we shift to combinatorial topology, and study cross-flips, i.e., local moves on balanced manifolds introduced by Izmestiev, Klee and Novik, which preserve both the coloring and the topological type. In chapter 4 we provide an explicit description and enumeration of an interesting subset of these moves and use it to prove a Pachner-type theorem. Indeed, we show that any two balanced combinatorial manifolds with boundary which are PL-homeomorphic can be transformed one into the other by a sequence of shellings and inverse shellings which preserve both the coloring and the topological type at each step. This solves a problem proposed by Izmestiev, Klee and Novik. Chapter 5 is devoted to the study of certain algebraic invariants of simplicial complexes in the balanced case. Here upper bounds for the graded Betti numbers of the Stanley-Reisner ring of balanced simplicial complexes are investigated in several level of generalities, and we show that they are sharper than in the general case. First, we employ Hochster formula to obtain inequalities for the case of arbitrary balanced complexes. Next, we focus on the balanced Cohen-Macaulay case and we obtain two upper bounds via two different strategies. Using similar ideas we also bound the Betti numbers in the linear strand of balanced normal d-pseudomanifolds, for d>2. Finally, we explicitly compute graded Betti numbers of the class of stacked cross-polytopal spheres, and conjecture that they provide a sharp upper bound for those of all balanced pseudomanifolds with the same dimension and number of vertices. In the last chapter, we implement cross-flips on balanced surfaces and 3-manifolds, and use this computer program to search for balanced manifolds on few vertices, possibly vertex-minimal. Reducing the barycentric subdivision of vertex minimal triangulations, we find a long list of balanced triangulations of interesting spaces on few vertices. Among those stand out a balanced vertex-minimal triangulation of the dunce hat (11-vertices) and of the 2- and 3-dimensional real projective space (9 and 16 vertices respectively). Using obstructions from knot theory and a careful choice of flips we find a balanced non-shellable 3-sphere and a balanced shellable non-vertex-decomposable 3-sphere on 28 and 22 vertices respectively. These are the smallest instances known in the literature.

We consider random simplicial complexes constructed on a Poisson point process within a convex set in a Euclidean space, especially the Vietoris-Rips complex and the Cech complex both of whose 1-skeleton is the Gilbert graph. We investigate at first the Vietoris-Rips complex by considering the volume-power functionals defined by summing powers of the volume of all k-dimensional faces in the complex. The asymptotic behaviour of these functionals is investigated as the intensity of the underlying Poisson point process tends to infinity and the distance parameter goes to zero. This behaviour is observed in different regimes. Univariate and multivariate central limit theorems are proven, and analogous results for the Cech complex are then given. Finally we provide a Poisson limit theorem for the components of the f-vector in the sparse regime.

No description available.