La théorie de l'homologie fournit des solutions nouvelles et efficaces pour régler le problème de trou de couverture dans les réseaux de capteurs sans fil. Ils sont basés sur deux objets combinatoires nommés complexe de Cech et complexe de Rips. Le complexe de Cech peut détecter l'intégralité des trous de couverture, mais il est très difficile à construire. Le complexe de Rips est facile à construire, mais il est imprécis dans certaines situations. Dans la première partie de cette thèse, nous choisissons la proportion de la surface de trous manqués par le complexe de Rips comme une mesure d'évaluer l'exactitude de la détection de trou de couverture basée sur l'homologie. Des expressions fermées pour les bornes inférieures et supérieures de la proportion sont dérivés. Les résultats de simulation sont bien compatibles avec les bornes inférieure et supérieure calculés analytiquement, avec des différences maximales de 0.5% et 3%. En outre, nous étendons l'analyse au cas de la sphère. Dans la deuxième partie, nous proposons d'abord un algorithme distribué basé sur les graphes pour détecter les trous non triangulaires. Cet algorithme présente une grande complexité. Nous proposons donc un autre algorithme distribué plus efficace basé sur l'homologie. Cet algorithme ne nécessite que des informations de 1- et 2-saut nœuds voisins et a la complexité O(n3) où n est le nombre maximum de nœuds voisins à 1 saut. Il peut détecter avec précision les cycles frontières d'environ 99% des trous de couverture dans environ 99% des cas. / Homology theory provides new and powerful solutions to address the coverage hole problem in wireless sensor networks (WSNs). They are based on two combinatorial objects named Cech complex and Rips complex. Cech complex can fully characterize coverage properties of a WSN (existence and locations of holes), but it is very difficult to construct. Rips complex is easy to construct but it may miss some coverage holes. In the first part of this thesis, we choose the proportion of the area of holes missed by Rips complex as a metric to evaluate the accuracy of homology based coverage hole detection. Closed form expressions for lower and upper bounds of the proportion are derived. Simulation results are well consistent with the analytical lower and upper bounds, with maximum differences of 0.5% and 3%. In addition, we extend the analysis to the sphere case. In the second part, we first propose a graph based distributed algorithm to detect non-triangular holes. This algorithm exhibits high complexity. We thus propose another efficient homology based distributed algorithm. This algorithm only requires 1- and 2-hop neighbour nodes information and has the worst case complexity O(n3) where n is the maximum number of 1-hop neighbour nodes. It can accurately detect the boundary cycles of about 99% coverage holes in about 99% cases.

In 1990, Fröberg presented a combinatorial classification of the quadratic square-free monomial ideals with linear resolutions. He showed that the edge ideal of a graph has a linear resolution if and only if the complement of the graph is chordal. Since then, a generalization of Fröberg's theorem to higher dimensions has been sought in order to classify all square-free monomial ideals with linear resolutions. Such a characterization would also give a description of all square-free monomial ideals which are Cohen-Macaulay. In this thesis we explore one method of extending Fröberg's result. We generalize the idea of a chordal graph to simplicial complexes and use simplicial homology as a bridge between this combinatorial notion and the algebraic concept of a linear resolution. We are able to give a generalization of one direction of Fröberg's theorem and, in investigating the converse direction, find a necessary and sufficient combinatorial condition for a square-free monomial ideal to have a linear resolution over fields of characteristic 2.

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

This thesis is comprised of three parts. The first part describes a novel framework for computing importance measures on graph vertices. The concept of a D-spectrum is introduced, based on vertex ranks within certain chains of nested sub-graphs. We show that the D- spectrum integrates the degree distribution and coreness information of the graph as two particular such chains. We prove that these spectra are realized as fixed points of certain monotone and contractive SDSs we call t-systems. Finally, we give a vertex deletion algorithm that efficiently computes D-spectra, and we illustrate their correlation with stochastic SIR-processes on real world networks. The second part deals with the topology of the intersection nerve for a bi-secondary structure, and its singular homology. A bi-secondary structure R, is a combinatorial object that can be viewed as a collection of cycles (loops) of certain at most tetravalent planar graphs. Bi-secondary structures arise naturally in the study of RNA riboswitches - molecules that have an MFE binary structural degeneracy. We prove that this loop nerve complex has a euclidean 3-space embedding characterized solely by H2(R), its second homology group. We show that this group is the only non-trivial one in the sequence and furthermore it is free abelian. The third part further describes the features of the loop nerve. We identify certain disjoint objects in the structure of R which we call crossing components (CC). These are non-trivial connected components of a graph that captures a particular non-planar embedding of R. We show that each CC contributes a unique generator to H2(R) and thus the total number of these crossing components in fact equals the rank of the second homology group. / Doctor of Philosophy / This Thesis is divided into three parts. The first part describes a novel mathematical framework for decomposing a real world network into layers. A network is comprised of interconnected nodes and can model anything from transportation of goods to the way the internet is organized. Two key numbers describe the local and global features of a network: the number of neighbors, and the number of neighbors in a certain layer, a node has. Our work shows that there are other numbers in-between the two, that better characterize a node. We also give explicit means of computing them. Finally, we show that these numbers are connected to the way information spreads on the network, uncovering a relation between the network’s structure and dynamics on said network. The last two parts of the thesis have a common theme and study the same mathematical object. In the first part of the two, we provide a new model for the way riboswtiches organize themselves. Riboswitches, are RNA molecules within a cell, that can take two mutually opposite conformations, depending on what function they need to perform within said cell. They are important from an evolutionary standpoint and are actively studied within that context, usually being modeled as networks. Our model captures the shapes of the two possible conformations, and encodes it within a mathematical object called a topological space. Once this is done, we prove that certain numbers that are attached to all topological spaces carry specific values for riboswitches. Namely, we show that the shapes of the two possible conformations for a riboswich are always characterized by a single integer. In the last part of the Thesis we identify what exactly in the structure of riboswitches contributes to this number being large or small. We prove that the more tangled the two conformations are, the larger the number. We can thus conclude that this number is directly proportional to how complex the riboswitch is.

Homologie simpliciale est un outil très efficace pour accéder à des informations importantes sur la topologie des réseaux sans fil, tels que : la couverture et la connectivité. Dans cette thèse, nous modélisons le réseau sans fil comme un déploiement aléatoire des cellules. Tout d’abord, nous introduisons un algorithme pour construire le complexe de Cech, qui décrit exactement la topologie du réseau. Ensuite, ˇ le complexe de Cech est utilisé dans des applications avancées. La première application est d’économiser ˇ l’énergie de transmission pour les réseaux sans fil. Cette application non seulement maximise la couverture de le réseau, mais réduit également la puissance de transmission. En même temps, la couverture et la puissance de transmission sont optimisées. La deuxième application est pour équilibrer la charge de trafic dans les réseaux sans fil. Cette application contrôle la puissance de transmission de chaque cellule dans le réseau, toujours sous contrainte de couverture. Avec la puissance d’émission contrôlée, les utilisateurs sont redirigés vers des cellules de charge plus faibles. Par conséquent, la charge du trafic est répartie entre lesdifférentes cellules. / Simplicial homology is a useful tool to access important information about the topology of wireless networks such as : coverage and connectivity. In this thesis, we model the wireless network as a random deployment of cells. Firstly, we introduce an algorithm to construct the Cech complex, which describes exactly the topology of the network. Then, the Cech complex is used in further applications. The first application is to save transmission power for wireless networks. This application not only maximizes the coverage of the network but also minimizes its transmission power. At the same time, the coverage and the transmission power are optimized. The second application is to balance the traffic load in wireless networks. This application controls the transmission power of each cell in the network, always under the coverage constraint. With the controlled transmission power, the users are redirected to connect to the lower traffic load cells. Consequentially, the balanced traffic load is obtained for the network.

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.

<p>U ovoj tezi razvijen je formalni sistem za dokazivanje teorema<br />incidencije u projektivnoj geometiji. Osnova sistema je Čeva/Menelaj<br />metod za dokazivanje teorema incidencije. Formalizacija o kojoj je<br />ovdje riječ izvedena je korišćenjem &Delta;-kompleksa, pa su tako u<br />disertaciji spojene oblasti logike, geometrije i algebarske<br />topologije. Aksiomatski sekventi proizilaze iz 2-ciklova &Delta;-kompleksa.<br />Definisana je Euklidska i projektivna interpretacija sekvenata i<br />dokazana je saglasnost i odlučivost sistema. Dati su primjeri<br />iščitavanja teorema incidencije iz dokazivih sekvenata sistema. U<br />tezi je data i procedura za provjeru da li je skup od n šestorki tačaka<br />aksiomatski sekvent.</p> / <p>In this thesis, a formal sequent system for proving incidence theorems in<br />projective geometry is introduced. This system is based on the<br />Ceva/Menelaus method for proving theorems. This formalization is performed<br />using &Delta;-complexes, so the areas of logic, geometry and algebraic topology<br />are combined in the dissertation. The axiomatic sequents of the system stem<br />from 2-cycles of &Delta;-complexes. The Euclidean and projective interpretations of<br />the sequents are defined and the decidability and soundness of the system<br />are proved. Patterns for extracting formulation and proof of the incidence<br />result from derivable sequents of system are exemplified. The procedure for<br />deciding if set of n sextuples represent an axiomatic sequent is presented<br />within the thesis.</p>

Let G be a finite graph with vertex set V and edge set E. A graph complex on G is an abstract simplicial complex consisting of subsets of E. In particular, we may interpret such a complex as a family of subgraphs of G. The subject of this thesis is the topology of graph complexes, the emphasis being placed on homology, homotopy type, connectivity degree, Cohen-Macaulayness, and Euler characteristic. We are particularly interested in the case that G is the complete graph on V. Monotone graph properties are complexes on such a graph satisfying the additional condition that they are invariant under permutations of V. Some well-studied monotone graph properties that we discuss in this thesis are complexes of matchings, forests, bipartite graphs, disconnected graphs, and not 2-connected graphs. We present new results about several other monotone graph properties, including complexes of not 3-connected graphs and graphs not coverable by p vertices. Imagining the vertices as the corners of a regular polygon, we obtain another important class consisting of those graph complexes that are invariant under the natural action of the dihedral group on this polygon. The most famous example is the associahedron, whose faces are graphs without crossings inside the polygon. Restricting to matchings, forests, or bipartite graphs, we obtain other interesting complexes of noncrossing graphs. We also examine a certain "dihedral" variant of connectivity. The third class to be examined is the class of digraph complexes. Some well-studied examples are complexes of acyclic digraphs and not strongly connected digraphs. We present new results about a few other digraph complexes, including complexes of graded digraphs and non-spanning digraphs. Many of our proofs are based on Robin Forman's discrete version of Morse theory. As a byproduct, this thesis provides a loosely defined toolbox for attacking problems in topological combinatorics via discrete Morse theory. In terms of simplicity and power, arguably the most efficient tool is Forman's divide and conquer approach via decision trees, which we successfully apply to a large number of graph and digraph complexes. / QC 20100622