<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

In the thesis we study two dimensional simplicial complexes and linear codes. We say that a linear code C over a field F is triangular representable if there exists a two dimensional simplicial complex ∆ such that C is a punctured code of the kernel ker ∆ of the incidence matrix of ∆ over F and dim C = dim ker ∆. We call this simplicial complex a geometric representation of C. We show that every linear code C over a primefield is triangular representable. In the case of finite primefields we construct a geometric representation such that the weight enumerator of C is obtained by a simple formula from the weight enumerator of the cycle space of ∆. Thus the geometric representation of C carries its weight enumerator. Our motivation comes from the theory of Pfaffian orientations of graphs which provides a polynomial algorithm for weight enumerator of the cut space of a graph of bounded genus. This algorithm uses geometric properties of an embedding of the graph into an orientable Riemann surface. Viewing the cut space of a graph as a linear code, the graph is thus a useful geometric representation of this linear code. We study embeddability of the geometric representations into Euclidean spaces. We show that every binary linear code has a geometric representation that can be embed- ded into R4 . We characterize...

Made available in DSpace on 2016-06-02T20:28:22Z (GMT). No. of bitstreams: 1 DissCAB.pdf: 645370 bytes, checksum: e59bde5eac8143ecef6b81fbeca6d9aa (MD5) Previous issue date: 2004-03-31 / Financiadora de Estudos e Projetos / In this work we present fundamental theory to establish the coordinates of the Kronecker Index, Cup and Cap Products in the finite Simplicial Complexes category in terms of chain and cochain. / Neste trabalho nós apresentamos a teoria fundamental para estabelecer as coordenadas do Índice de Kronecker, Produtos Cup e Cap na categoria dos complexos simpliciais finitos em termos de cadeia e cocadeia.

Le but de cette thèse est d’étendre les résultats de l'article [B-M] sur les relations entre variétés moment-angle et variétés complexes. On s'intéressera ici aux variétés moment-angle issues d'une décomposition simpliciale (et non simplement polytopale) de la sphère. On cherchera ensuite à utiliser la relation entre ces deux types d’objets pour comprendre la topologie de certaines variétés complexes.[B-M] F.Bosio, L.Meersseman, Real quadrics in Cn, complex manifolds and polytopes, Acta Mathematica, 197 (2006), n° 1, 53 -- 127. / The aim of this thesis is to extend the results of the article [B-M] on the relations between moment-angle complexes and complex manifolds. We will focus here on moment-angle complexes defined by a simplicial (not only polytopal) decomposition of the sphere. We will also seek to use the relationship between these two kinds of objects to be understand the topology of several complex manifolds. [B-M] F.Bosio, L.Meersseman, Real quadrics in Cn, complex manifolds and polytopes, Acta Mathematica, 197 (2006), n° 1, 53 -- 127.

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.

<p>Applied topology is a rapidly growing discipline aiming at using ideas coming from algebraic topology to solve problems in the real world, including analyzing point cloud data, shape analysis, etc. Semi-algebraic geometry deals with studying properties of semi-algebraic sets that are subsets of $\mathbb{R}^n$ and defined in terms of polynomial inequalities. Semi-algebraic sets are ubiquitous in applications in areas such as modeling, motion planning, etc. Developing efficient algorithms for computing topological invariants of semi-algebraic sets is a rich and well-developed field.</p> <p>However, applied topology has thrown up new invariants---such as persistent homology and barcodes---which give us new ways of looking at the topology of semi-algebraic sets. In this thesis, we investigate the interplay between these two areas. We aim to develop new efficient algorithms for computing topological invariants of semi-algebraic sets, such as persistent homology, and to develop new mathematical tools to make such algorithms possible.</p>

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.

京都大学 / 新制・課程博士 / 博士(理学) / 甲第24398号 / 理博第4897号 / 新制||理||1700(附属図書館) / 京都大学大学院理学研究科物理学・宇宙物理学専攻 / (主査)教授 佐藤 昌利, 教授 佐々 真一, 准教授 戸塚 圭介 / 学位規則第4条第1項該当 / Doctor of Science / Kyoto University / DGAM