This dissertation examines the topological properties of simplicial complexes that arise from two distinct combinatorial objects. In 2003, A. Björner and M. de Longueville proved that the neighborhood complex of the stable Kneser graph SGn,k is homotopy equivalent to a k-sphere. Further, for n = 2 they showed that the neighborhood complex deformation retracts to a subcomplex isomorphic to the associahedron. They went on to ask whether or not, for all n and k, the neighborhood complex of SGn,k contains as a deformation retract the boundary complex of a simplicial polytope. Part one of this dissertation provides a positive answer to this question in the case k = 2. In this case it is also shown that, after partially subdividing the neighborhood complex, the resulting complex deformation retracts onto a subcomplex arising as a polyhedral boundary sphere that is invariant under the action induced by the automorphism group of SGn,2. Part two of this dissertation studies simplicial complexes that arise from non-attacking rook placements on a subclass of Ferrers boards that have ai rows of length i where ai > 0 and i ≤ n for some positive integer n. In particular, enumerative properties of their facets, homotopy type, and homology are investigated.

The optimal number of faces in cubical complexes which lie in cubes refers to the maximum number of faces that can be constructed from a certain number of faces of lower dimension, or the minimum number of faces necessary to construct a certain number of faces of higher dimension. If <i>m</i> is the number of faces of <i>r</i> in a cubical complex, and if s > r(s < r), then the maximum(minimum) number of faces of dimension s that the complex can have is m_(s/r) +. (m-m_(r/r))^(s/r), in terms of upper and lower semipowers. The corresponding formula for simplicial complexes, proved independently by J. B. Kruskal and G. A. Katona, is m^(s/r). A proof of the formula for cubical complexes is given in this paper, of which a flawed version appears in a paper by Bernt Lindstrijm. The n-tuples which satisfy the optimaiity conditions for cubical complexes which lie in cubes correspond bijectively with f-vectors of cubical complexes. / Master of Science

Nous étudions les triangulations dans des espaces de courbure négative constante, en théorie et en pratique. Ce travail est motivé par des applications dans des domaines variés. Nous considérons les complexes de Delaunay et les diagrammes de Voronoï dans la boule de Poincaré, modèle conforme de l'espace hyperbolique, en dimension quelconque. Nous utilisons l'espace des sphères pour la description des algorithmes. Nous étudions aussi les questions algébriques et arithmétiques et observons que les calculs effectués sont rationnels. Les démonstrations sont basées sur des raisonnements géométriques et n'utilisent aucune formulation analytique de la distance hyperbolique. Nous présentons une implantation complète, exacte et efficace en dimension deux. Le code est développé en vue d'une intégration dans la bibliothèque CGAL, qui permettra une diffusion à un large public. Nous étudions ensuite les triangulations de Delaunay des surfaces hyperboliques fermées. Nous définissons une triangulation comme un complexe simplicial afin de permettre l'adaptation de l'algorithme incrémentiel connu pour le cas euclidien. Le cœur de l'approche consiste à montrer l'existence d'un revêtement fini dans lequel les fibres définissent toujours une triangulation de Delaunay. Nous montrons une condition suffisante sur la longueur des boucles non contractiles du revêtement. Dans le cas particulier de la surface de Bolza, nous proposons une méthode pour construire un tel revêtement, en étudiant les sous groupes distingués du groupe fuchsien définissant la surface. Nous considérons des aspects liés à l'implantation. / We study triangulations of spaces of constant negative curvature -1 from both theoretical and practical points of view. This is originally motivated by applications in various fields such as geometry processing and neuro mathematics. We first consider Delaunay complexes and Voronoi diagrams in the Poincaré ball, a conformal model of the hyperbolic space, in any dimension. We use the framework of the space of spheres to give a detailed description of algorithms. We also study algebraic and arithmetic issues, observing that only rational computations are needed. All proofs are based on geometric reasoning, they do not resort to any use of the analytic formula of the hyperbolic distance. We present a complete, exact, and efficient implementation of the Delaunay complex and Voronoi diagram in the 2D hyperbolic space. The implementation is developed for future integration into the CGAL library to make it available to a broad public. Then we study the problem of computing Delaunay triangulations of closed hyperbolic surfaces. We define a triangulation as a simplicial complex, so that the general incremental algorithm for Euclidean Delaunay triangulations can be adapted. The key idea of the approach is to show the existence of a finite-sheeted covering space for which the fibers always define a Delaunay triangulation. We prove a sufficient condition on the length of the shortest non-contractible loops of the covering space. For the specific case of the Bolza surface, we propose a method to actually construct such a covering space, by studying normal subgroups of the Fuchsian group defining the surface. Implementation aspects are considered.

Desenvolvemos as ideias centrais da Homologia Simplicial e provamos a invariância topológica dos grupos de homologia para espaços homeomorfos. Discutimos também a invariância topológica da característica de Euler-Poincaré mostrando a sua relação com os grupos de homologia através dos números de Betti. Adicionalmente apresentamos conceitos da Álgebra Abstrata, especificamente da teoria de Grupos, importantes para o entendimento formal da álgebra homológica. Ao final, propomos atividades didáticas com objetivo de trazer as ideias de triangulação e invariância topológica ao contexto da sala de aula. / We develop central ideas of Simplicial Homology and prove the topological invariance of homology groups for homeomorphic spaces. We also discuss topological invariance of Euler- Poincaré characteristic showing its relation with the homology groups through Betti numbers. In addition, we present concepts of abstract algebra, specifically of group theory, which are important to formal understanding of homological algebra. In the end, we propose didactic activities in order to bring the ideas of triangulation and topological invariance to context of math classes on basic education.

Submitted by Marlene Santos (marlene.bc.ufg@gmail.com) on 2016-07-13T20:13:32Z No. of bitstreams: 2 Dissertação - Mauricio Silva Louzeiro - 2016.pdf: 1453255 bytes, checksum: c23898f8b30d7250d9fc245034078281 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Approved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2016-07-14T13:28:30Z (GMT) No. of bitstreams: 2 Dissertação - Mauricio Silva Louzeiro - 2016.pdf: 1453255 bytes, checksum: c23898f8b30d7250d9fc245034078281 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Made available in DSpace on 2016-07-14T13:28:30Z (GMT). No. of bitstreams: 2 Dissertação - Mauricio Silva Louzeiro - 2016.pdf: 1453255 bytes, checksum: c23898f8b30d7250d9fc245034078281 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Previous issue date: 2016-03-04 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / In this work, we will study a new strategy to minimize a convex function on a simplicial cone. This method consists in to obtain the solution of a minimization problem through the root of a semi-smooth equation associated to its optimality conditions. To nd this root, we use the semi-smooth version of the Newton's method, where the derivative of the function that de nes the semi-smooth equation is replaced by a convenient Clarke subgradient. For the case that the function is quadratic, we will see that it allows us to have weaker conditions for the convergence of the sequence generated by the semi-smooth Newton's method. Motivated by this new minimization strategy we will also use the semi-smooth Newton's method to nd roots of two special semi-smooth equations, one associated to x+ and the another one associated to jxj. / Neste trabalho, estudaremos uma nova estrat egia para minimizar uma fun c~ao convexa sobre um cone simplicial. Este m etodo consiste em obter a solu c~ao do problema de minimiza c~ao atrav es da raiz de uma equa c~ao semi-suave associada as suas condi c~oes de otimalidade. Para encontrar essa raiz, usaremos uma vers~ao semi-suave do m etodo de Newton, onde a derivada da fun c~ao que de ne a equa c~ao semi-suave e substitu da por um subgradiente de Clarke conveniente. Para o caso em que a fun c~ao e quadr atica, veremos que e poss vel obter condi c~oes mais fracas para a converg^encia da sequ^encia gerada pelo m etodo de Newton semi-suave. Motivados por esta nova estrat egia de minimiza c~ao tamb em usaremos o m etodo de Newton semi-suave para encontrar ra zes de dois tipos espec cos de equa c~oes semi-suaves, uma associada a x+ e a outra associada a jxj.

Making use of algebraic and combinatorial techniques, we study two topics: the arithmetic degree of squarefree strongly stable ideals and the h-vectors of matroid complexes. For a squarefree monomial ideal, I, the arithmetic degree of I is the number of facets of the simplicial complex which has I as its Stanley-Reisner ideal. We consider the case when I is squarefree strongly stable, in which case we give an exact formula for the arithmetic degree in terms of the minimal generators of I as well as a lower bound resembling that from the Multiplicity Conjecture. Using this, we can produce an upper bound on the number of minimal generators of any Cohen-Macaulay ideals with arbitrary codimension extending Dubreil’s theorem for codimension 2. A matroid complex is a pure complex such that every restriction is again pure. It is a long-standing open problem to classify all possible h-vectors of such complexes. In the case when the complex has dimension 1 we completely resolve this question and we give some partial results for higher dimensions. We also prove the 1-dimensional case of a conjecture of Stanley that all matroid h-vectors are pure O-sequences. Finally, we completely characterize the Stanley-Reisner ideals of matroid complexes.

Let V denote a vector space of finite positive dimension. An ordered triple of linear operators on V is said to be a Leonard triple whenever for each choice of element of the triple there exists a basis of V with respect to which the matrix representing the chosen element is diagonal and the matrices representing the other two elements are irreducible tridiagonal. A Leonard triple is said to be modular whenever for each choice of element there exists an antiautomorphism of End(V) which fixes the chosen element and swaps the other two elements. We study combinatorial structures associated with Leonard triples and modular Leonard triples. In the first part we construct a simplicial complex of Leonard triples. The simplicial complex of a Leonard triple is the smallest set of linear operators which contains the given Leonard triple with the property that if two elements of the set are part of a Leonard triple, then the third element of the triple is also in the set. In the second part we construct a Hamming association scheme from modular Leonard triples using a method used previously in the context of Grassmanian codes.

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.

- / -

Placement games are a subclass of combinatorial games which are played on graphs. In this thesis, we demonstrate that placement games could be considered as games played on simplicial complexes. These complexes are constructed using square-free monomials. We define new classes of placement games and the notion of Doppelgänger. To aid in exploring the simplicial complex of a game, we introduce the bipartite flip and develop tools to compare known bounds on simplicial complexes (such as the Kruskal-Katona bounds) with bounds on game complexes.