Th. 3e cycle--Math. pures--Grenoble 1, 1984. N°: 51.

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.

No description available.

No description available.

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.

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+).

A major impediment to scientific progress in many fields is the inability to make sense of the huge amounts of data that have been collected via experiment or computer simulation. This dissertation provides tools to visualize, represent, and analyze the collection of sensors and data all at once in a single combinatorial geometric object. Encoding and translating heterogeneous data into common language are modeled by supporting objects. In this methodology, the behavior of the system based on the detection of noise in the system, possible failure in data exchange and recognition of the redundant or complimentary sensors are studied via some related geometric objects. Applications of the constructed methodology are described by two case studies: one from wildfire threat monitoring and the other from air traffic monitoring. Both cases are distributed (spatial and temporal) information systems. The systems deal with temporal and spatial fusion of heterogeneous data obtained from multiple sources, where the schema, availability and quality vary. The behavior of both systems is explained thoroughly in terms of the detection of the failure in the systems and the recognition of the redundant and complimentary sensors. A comparison between the methodology in this dissertation and the alternative methods is described to further verify the validity of the sheaf theory method. It is seen that the method has less computational complexity in both space and time.

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.

Dans l'optique d'étudier les modules de génération finie sur des algèbres de dimension finie, il a été développé ces dernières années une méthode diagramatique, essentiellement due à P. Gabriel, basée sur des carquois, c'est-à-dire sur des graphes orientées finis. Plus précisément, il a été démontré que pour toute algèbre A sobre de dimension finie sur un corps k algébriquement clos, il existe un carquois unique Q et au moins un idéal I admissible de l'algèbre kQ, l'algèbre des chemins de Q, tels que A soit isomorphe à kQ=I. Un tel couple (Q; I) est nommé une présentation de A par carquois et relations. Pour chaque paire (Q; I), nous pouvons définir un groupe fondamental Pi1(Q; I). En général, cependant, différentes présentations d'une même algèbre peuvent conduire à des groupes fondamentaux difféerents. Ainsi, une algèbre dont toutes les présentations donnent un groupe fondamental trivial est appelée simplement connexe. L'importance des algèbres simplement connexes dans la théorie des représentations d'algèbres réside dans le fait que souvent il est possible de réduire, avec l'aide des recouvrements, l'étude des modules indécomposables d'une algèbre à ceux d'une algèbre simplement connexe bien choisie. Le premier résultat consiste à donner une vision géométrique du groupe fondamental pour une certaine classe d'algèbre : les algèbres d'incidence. Ces algèbres ont une particularité : leur groupe fondamental ne dépend pas du choix de la présentation. Ainsi, à chaque algèbre d'incidence, il est possible d'associer un groupe fondamental algébrique. Par ailleurs, à partir de ce poset, est possible de construire un complexe simplicial qui possède quant à lui un groupe fondamental topologique. Nous prouvons, ici, que ces groupes sont isomorphes. Ce lien permet non seulement d'adapter certains théorèmes de topologie tel que le théorème de Van Kampen, mais également de faire le lien entre des résultats déjà établis en topologie et d'autres en théorie des représentations. Dans un deuxième temps, afn de donner une vision géométrique de tout groupe fondamen- tal algébrique, nous avons associé à toute présentation (Q; I) d'algèbre une algèbre d'incidence A dont le groupe fondamental a la particularité, d'après le résultat précédent, de se réaliser géométriquement. Nous montrons ensuite que les groupes fondamentaux précédents s'insèrent dans la suite exacte : 1 --> H --> Pi1(Q; I) --> Pi1(A) --> 1 où H est un sous-groupe décrit par générateur et relations. Nous donnons également de nom- breux cas où le sous groupe H est trivial. Enfin, nous donnons un algorithme de calcul du groupe fondamental, qui permet de présenter rapidement le groupe fondamental par générateurs et relations. Pour calculer le groupe fondamental d'un couple (Q; I), nous montrons qu'il est isomorphe au groupe fondamental d'un couple (Q0; I0) où Q0 contient un sommet de moins que Q. Ainsi en réitérant le processus, le groupe fondamental Pi1(Q; I) est isomorphe au groupe fondamental d'un carquois ne contenant qu'un seul sommet, ce qui donne une présentation par générateurs et relations.

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.