Search

Message-passing algorithms consist of a parallelised computing scheme to estimate the marginals of a high-dimensional probability distribution. They have been used in various areas where the statistics of a large number of interacting variables have to be studied, including statistical physics, artificial intelligence, decoding in information theory. This thesis desctibes the algebraic and topological structures in which message-passing algorithms naturally take place. In most applications, the probability distribution p is defined by a Markov field or graphical model, i.e. as a product of local factors depending only on small subsets of interacting variables. Equivalently, the total energy H = - ln p (or log-likelihood) is a sum of local interaction potentials. Embedding potentials as the 0-degree subspace of a chain complex of local observables, we show that this constraint is equivalent to assuming a one-to-one parametrisation of total energies by homology classes of interaction potentials. The 1-chains of this complex are statistical analogs of heat fluxes. The evolution of potentials up to the boundary of a heat flux, preserving total energy, produces new belief propagation algorithms as continuous-time diffusion equations. The consistency of pseudo-marginals one seeks to approximate is reciprocally translated by a cohomological constraint, demanding that a collection of local probability distributions has a vanishing differential. The local potentials and local distributions form a pair of dual variables put in correspondence by a smooth non-linear functional, essentially composing the exponential with a sum over subsets, called zeta transform in combinatorics. Pairs at the intersection of the energy conservation and marginal consistency constraint surfaces are shown to be in correspondence with both the stationary points of belief propagation algorithms and the critical points of a local approximation of free energy, computed by the Bethe-Kikuchi combinatorial method, a truncation of the Möbius inversion of the zeta transform.; Les algorithmes à propagation de messages constituent un schéma de calcul parallèle pour estimer les marginales d’une loi de probabilité de haute dimension. Ils ont été employés dans des domaines variés où la statistique d’un grand nombre de variables en interaction doit être étudiée, comme la physique statistique, l’intelligence artificielle, le décodage en théorie de l’information. Cette thèse décrit les structures algébriques et topologiques naturelles où se déroulent la propagation de messages. Dans la plupart des applications, la loi de probabilité p est définie par un champ de Markov ou modèle graphique, i.e. par un produit de facteurs locaux qui ne dépendent que d’un petit sous-ensemble de variables en interaction. De manière équivalente, l’énergie totale H = ln p (ou log-vraisemblance) est une somme de potentiels d’interaction locaux. Nous montrons que cette contrainte est équivalente à l’existence d’une paramétrisation biunivoque de l’énergie totale par les classes d’homologie de potentiels locaux, en immergeant les potentiels comme sous-espace de degré 0 d’un complexe de chaînes d’observables locales. Les 1-chaînes de ce complexe sont un analogue statistique des flux de chaleur. L’évolution de potentiels à un bord de flux de chaleur près, préservant l’énergie totale, produit de nouveaux algorithmes à propagation de croyances comme des équations de diffusion à temps continu. La consistance des pseudo-marginales que l’on cherche à approximer est réciproquement traduite par une contrainte cohomologique, demandant que la collection de probabilités locales ait une différentielle nulle. Les potentiels locaux et les probabilités locales forment une paire de variables duales, reliées par une fonctionnelle lisse et non-linéaire, composant essentiellement l’exponentielle avec une somme sur les sous-parties appelée transformée zeta en combinatoire. Les paires à l’intersection des surfaces de contrainte associées à la conservation de l’énergie et à la consistance marginale respectivement sont mises en correspondance avec les points stationnaires des algorithmes à propagation de croyance d’une part, et avec les points critiques d’une approximation locale de l’énergie libre, obtenue par la méthode combinatoire de Bethe-Kikuchi (en tronquant la transformée de Möbius, inverse de la transformée zeta) d’autre part.

In this thesis, we will work with the nodal sets of Laplace eigenfunctions on a few simple manifolds, like the sphere and the flat torus. We will obtain bounds on the total Betti number of the nodal set that depend on the corresponding eigenvalue. Our work generalize Courant's theorem., Dans ce mémoire, nous travaillons sur les ensembles nodaux de combinaisons de fonctions propres du laplacien, particulièrement sur la sphère et le tore plat. On bornera les nombres de Betti de ces ensembles en fonction de la valeur propre maximale. D'une certaine façon, cela généralise le fameux théorème de Courant.

Let $F_n$ be the free group on $n$ generators. Consider the group $IA_n$ of automorpisms of $F_n$ acting trivially on its abelianization. There are two canonical filtrations on $IA_n$: the first one is its lower central series $\Gamma_*$; the second one is the Andreadakis filtration $\mathcal A_*$, defined from the action on $F_n$. Andreadakis asked if and how these filtrations were different. We begin by describing a framework adapted to the study of such filtrations and their counterparts on group algebras. We then study several versions of the problem. In particular, we look at its restriction to some subgroups of $IA_n$ : we show that the two filtration coïncide when restricted to the triangular subroups and to braid groups. We also consider a stable version of the problem : we establish that the canonical morphism between the associated graded Lie rings is surjective when $n$ is big enough compared to a fixed degree. We also investigate a $p$-restricted version of the Andreadakis problem, and provide a calculation of the Lie algebra of the classical congruence group.Our methods are algebraic in nature. The tools come from combinatorial group theory and the study of mapping class groups; we often introduce some categorical langage to reformulate them.

Algebraic topology, which is as an abstract domain of mathematics, can bring new concepts in the execution of the image processing tasks. Indeed, these tasks might be complex and limited by different factors such as the need of prior parameters, the influence of the background, the superposition of objects. In this thesis, we propose methods derived from algebraic topology that differ from classical image processing methods by integrating local information at global scales through topological invariants. A first method of image segmentation was developed by adding topological characteristics calculated through persistent homology to classical statistical characteristics. Another method based on topological complexes built from pixels was developed with the purpose to segment objects in 2D and 3D images. This method allows to segment objects in multidimensional images but also to provide an answer to known issues in object segmentation remaining robust regarding the noise and the variability of the background. Our method can be extended to large scale images by using the superpixels concept. We also showed that the relative version of homology can be used effectively to detect the movement of objects in image sequences. This method can detect and follow objects that appear and disappear in a video sequence from the beginning to the end of the sequence. Finally, we lay the foundations of a set of methods of image analysis based on sheaf theory that allows the merging of local data into a coherent whole. Moreover, we propose a second approach that allows to understand and interpret scale analysis and localization by using the sheaves cohomology.; La topologie algébrique, bien que domaine abstrait des mathématiques, apporte de nouveaux concepts pour le traitement d'images. En effet, ces tâches sont complexes et restent limitées par différents facteurs tels que la nécessité d’utiliser un paramétrage, l'influence de l'arrière-plan ou la superposition d'objets. Nous proposons ici des méthodes dérivées de la topologie algébrique qui diffèrent des méthodes classiques de traitement d'images par l’intégration d’informations locales vers des échelles globales grâce à des invariants topologiques. Une première méthode de segmentation d'images a été développée en ajoutant aux caractéristiques statistiques classiques d’autres de nature topologique calculées par homologie persistante. Une autre méthode basée sur des complexes topologiques a été développée dans le but de segmenter les objets dans des images 2D et 3D. Cette méthode segmente des objets dans des images multidimensionnelles et fournit une réponse à certains problèmes habituels en restant robuste vis à vis du bruit et de la variabilité de l'arrière-plan. Son application aux images de grande taille peut se faire en utilisant des superpixels. Nous avons également montré que l'homologie relative détecte le mouvement d’objets dans une séquence d'images qui apparaissent et disparaissent du début à la fin. Enfin, nous posons les bases d’un ensemble de méthodes d'analyse d'images basé sur la théorie des faisceaux qui permet de fusionner des données locales en un ensemble cohérent. De plus, nous proposons une seconde approche qui permet de comprendre et d'interpréter la structure d’une image en utilisant les invariants fournis par la cohomologie des faisceaux.

Algebraic topology, which is as an abstract domain of mathematics, can bring new concepts in the execution of the image processing tasks. Indeed, these tasks might be complex and limited by different factors such as the need of prior parameters, the influence of the background, the superposition of objects. In this thesis, we propose methods derived from algebraic topology that differ from classical image processing methods by integrating local information at global scales through topological invariants. A first method of image segmentation was developed by adding topological characteristics calculated through persistent homology to classical statistical characteristics. Another method based on topological complexes built from pixels was developed with the purpose to segment objects in 2D and 3D images. This method allows to segment objects in multidimensional images but also to provide an answer to known issues in object segmentation remaining robust regarding the noise and the variability of the background. Our method can be extended to large scale images by using the superpixels concept. We also showed that the relative version of homology can be used effectively to detect the movement of objects in image sequences. This method can detect and follow objects that appear and disappear in a video sequence from the beginning to the end of the sequence. Finally, we lay the foundations of a set of methods of image analysis based on sheaf theory that allows the merging of local data into a coherent whole. Moreover, we propose a second approach that allows to understand and interpret scale analysis and localization by using the sheaves cohomology., La topologie algébrique, bien que domaine abstrait des mathématiques, apporte de nouveaux concepts pour le traitement d'images. En effet, ces tâches sont complexes et restent limitées par différents facteurs tels que la nécessité d’utiliser un paramétrage, l'influence de l'arrière-plan ou la superposition d'objets. Nous proposons ici des méthodes dérivées de la topologie algébrique qui diffèrent des méthodes classiques de traitement d'images par l’intégration d’informations locales vers des échelles globales grâce à des invariants topologiques. Une première méthode de segmentation d'images a été développée en ajoutant aux caractéristiques statistiques classiques d’autres de nature topologique calculées par homologie persistante. Une autre méthode basée sur des complexes topologiques a été développée dans le but de segmenter les objets dans des images 2D et 3D. Cette méthode segmente des objets dans des images multidimensionnelles et fournit une réponse à certains problèmes habituels en restant robuste vis à vis du bruit et de la variabilité de l'arrière-plan. Son application aux images de grande taille peut se faire en utilisant des superpixels. Nous avons également montré que l'homologie relative détecte le mouvement d’objets dans une séquence d'images qui apparaissent et disparaissent du début à la fin. Enfin, nous posons les bases d’un ensemble de méthodes d'analyse d'images basé sur la théorie des faisceaux qui permet de fusionner des données locales en un ensemble cohérent. De plus, nous proposons une seconde approche qui permet de comprendre et d'interpréter la structure d’une image en utilisant les invariants fournis par la cohomologie des faisceaux.

In a first part, we study Voronov’s "Swiss-Cheese" operad SC2, which governs the action of a D2-algebra on a D1-algebra. We build a model in groupoids of this operad and we describe algebras over this model in a manner similar to the classical description of algebras over H*(SC). We extend our model into a rational model which depends on a Drinfeld associator, and we compare this new model to the one that we would get if the operad SC were formal. In a second part, we study configuration spaces of closed smooth simply connected manifolds. We prove over R a conjecture of Lambrechts–Stanley which describes a mode of such configuration spaces, and we obtain as corollary their real homotopy invariance. Moreover, using Kontsevich’s proof of the formality of the operads Dn, we obtain that this model is compatible with the action of the Fulton–MacPherson operad when the manifold is framed. This allows us to explicitly compute the factorization homology of such a manifold. Finally, in a third part, we expand this result to a large class of manifolds with boundary. We first use a chain-level Poincaré–Lefschetz duality result to compute the homology of the configuration spaces of these manifolds, then we reuse the methods of the second chapter to obtain our model, which is compatible with the action of the Swiss-Cheese operad SCn.

Nous introduisons dans ce travail une généralisation de la notion d'algorithme de planification de mouvement à un langage formel sur un alphabet infini X: Nous definissons ensuite la notion d'algorithme de plan-ification de mouvement généré par une grammaire hors contexte et celle d'algorithme de planification de mouvement contrôlé par automate. Nous définissons ensuite la complexité topologique associée à un langage formel et celle controlée par un automate. En examinant des cas particuliers nous retrouvons quelques résultats établit par M. FARBER[1], YULI B. RUDYAK [6] [8]...

International audience

Distributed consensus algorithms are iterative algorithms of low complexity where neighboring sensors interact with each other to reach an agreement without coordinating unit. As the nodes in a wireless sensor network have limited computing power and limited battery, these distributed algorithms must reach a consensus in a short time and with little message exchange. The first part of this thesis is based on the study and comparison of different consensus algorithms synchronously and asynchronously in terms of convergence speed and communication rates. The second part of our work concerns the application of these consensus algorithms to the problem of detecting coverage holes in wireless sensor networks. This coverage problem also provides the context for the continuation of our work. This problem is described as how a region of interest is monitored by sensors. Different geometrical approaches have been proposed but are limited by the need to know exactly the position of the sensors; but this information may not be available if the locating devices such as GPS are not on the sensors. From the mathematical tool called algebraic topology, we have developed a distributed algorithm of coverage hole detection searching a harmonic function of a network, that is to say canceling the operator of the 1-dimensional Laplacian. This harmonic function is connected to the homology group H1 which identifies the coverage holes. Once a harmonic function obtained, detection of the holes is realized by a simple random walk in the network.; Les algorithmes distribués de consensus sont des algorithmes itératifs de faible complexité où les nœuds de capteurs voisins interagissent les uns avec les autres pour parvenir à un accord commun sans unité coordinatrice. Comme les noeuds dans un réseau de capteurs sans fil ont une puissance de calcul et une batterie limitées, ces algorithmes distribués doivent parvenir à un consensus en peu de temps et avec peu d’échange de messages. La première partie de cette thèse est basée sur l’étude et la comparaison des différents algorithmes de consensus en mode synchrone et asynchrone en termes de vitesse de convergence et taux de communications. La seconde partie de nos travaux concerne l’application de ces algorithmes de consensus au problème de la détection de trous de couverture dans les réseaux de capteurs sans fil. Ce problème de couverture fournit aussi le contexte de la suite de nos travaux. Il se décrit comme étant la façon dont une région d’intérêt est surveillée par des capteurs. Différentes approches géométriques ont été proposées mais elles sont limitées par la nécessité de connaitre exactement la position des capteurs ; or cette information peut ne pas être disponible si les dispositifs de localisation comme par exemple le GPS ne sont pas sur les capteurs. À partir de l’outil mathématique appelé topologie algébrique, nous avons développé un algorithme distribué de détection de trous de couverture qui recherche une fonction harmonique d’un réseau, c’est-à-dire annulant l’opérateur du Laplacien de dimension 1. Cette fonction harmonique est reliée au groupe d’homologie H1 qui recense les trous de couverture. Une fois une fonction harmonique obtenue, la détection des trous se réalise par une simple marche aléatoire dans le réseau.

The goal of this thesis is to prove that π4(S3) ≃ Z/2Z in homotopy type theory. In particular it is a constructive and purely homotopy-theoretic proof. We first recall the basic concepts of homotopy type theory, and we prove some well-known results about the homotopy groups of spheres: the computation of the homotopy groups of the circle, the triviality of those of the form πk(Sn) with k < n, and the construction of the Hopf fibration. We then move to more advanced tools. In particular, we define the James construction which allows us to prove the Freudenthal suspension theorem and the fact that there exists a natural number n such that π4(S3) ≃ Z/nZ. Then we study the smash product of spheres, we construct the cohomology ring of a space, and we introduce the Hopf invariant, allowing us to narrow down the n to either 1 or 2. The Hopf invariant also allows us to prove that all the groups of the form π4n−1(S2n) are infinite. Finally we construct the Gysin exact sequence, allowing us to compute the cohomology of CP2 and to prove that π4(S3) ≃ Z/2Z and that more generally πn+1(Sn) ≃ Z/2Z for every n ≥ 3; L’objectif de cette thèse est de démontrer que π4(S3) ≃ Z/2Z en théorie des types homotopiques. En particulier, c’est une démonstration constructive et purement homotopique. On commence par rappeler les concepts de base de la théorie des types homotopiques et on démontre quelques résultats bien connus sur les groupes d’homotopie des sphères : le calcul des groupes d’homotopie du cercle, le fait que ceux de la forme πk(Sn) avec k < n sont triviaux et la construction de la fibration de Hopf. On passe ensuite à des outils plus avancés. En particulier, on définit la construction de James, ce qui nous permetde démontrer le théorème de suspension de Freudenthal et le fait qu’il existe un entier naturel n tel que π4(S3) ≃ Z/2Z. On étudie ensuite le produit smash des sphères, on construit l’anneau de cohomologie des espaces et on introduit l’invariant de Hopf, ce qui nous permet de montrer que n est égal soit à 1, soit à 2. L’invariant de Hopf nous permet également de montrer que tous les groupes de la forme π4n−1(S2n) sont infinis. Finalement, on construit la suite exacte de Gysin, ce qui nous permet de calculer la cohomologie de CP2 et de démontrer que π4(S3) ≃ Z/2Z, et que plus généralement on a πn+1(Sn) ≃ Z/2Z pour tout n ≥ 3

Distributed consensus algorithms are iterative algorithms of low complexity where neighboring sensors interact with each other to reach an agreement without coordinating unit. As the nodes in a wireless sensor network have limited computing power and limited battery, these distributed algorithms must reach a consensus in a short time and with little message exchange. The first part of this thesis is based on the study and comparison of different consensus algorithms synchronously and asynchronously in terms of convergence speed and communication rates. The second part of our work concerns the application of these consensus algorithms to the problem of detecting coverage holes in wireless sensor networks. This coverage problem also provides the context for the continuation of our work. This problem is described as how a region of interest is monitored by sensors. Different geometrical approaches have been proposed but are limited by the need to know exactly the position of the sensors; but this information may not be available if the locating devices such as GPS are not on the sensors. From the mathematical tool called algebraic topology, we have developed a distributed algorithm of coverage hole detection searching a harmonic function of a network, that is to say canceling the operator of the 1-dimensional Laplacian. This harmonic function is connected to the homology group H1 which identifies the coverage holes. Once a harmonic function obtained, detection of the holes is realized by a simple random walk in the network., Les algorithmes distribués de consensus sont des algorithmes itératifs de faible complexité où les nœuds de capteurs voisins interagissent les uns avec les autres pour parvenir à un accord commun sans unité coordinatrice. Comme les noeuds dans un réseau de capteurs sans fil ont une puissance de calcul et une batterie limitées, ces algorithmes distribués doivent parvenir à un consensus en peu de temps et avec peu d’échange de messages. La première partie de cette thèse est basée sur l’étude et la comparaison des différents algorithmes de consensus en mode synchrone et asynchrone en termes de vitesse de convergence et taux de communications. La seconde partie de nos travaux concerne l’application de ces algorithmes de consensus au problème de la détection de trous de couverture dans les réseaux de capteurs sans fil. Ce problème de couverture fournit aussi le contexte de la suite de nos travaux. Il se décrit comme étant la façon dont une région d’intérêt est surveillée par des capteurs. Différentes approches géométriques ont été proposées mais elles sont limitées par la nécessité de connaitre exactement la position des capteurs ; or cette information peut ne pas être disponible si les dispositifs de localisation comme par exemple le GPS ne sont pas sur les capteurs. À partir de l’outil mathématique appelé topologie algébrique, nous avons développé un algorithme distribué de détection de trous de couverture qui recherche une fonction harmonique d’un réseau, c’est-à-dire annulant l’opérateur du Laplacien de dimension 1. Cette fonction harmonique est reliée au groupe d’homologie H1 qui recense les trous de couverture. Une fois une fonction harmonique obtenue, la détection des trous se réalise par une simple marche aléatoire dans le réseau.

We propose in this thesis to characterize variability quantitatively at various scales during embryogenesis. We use a combination of mathematical models and experimental results. In the first part, we use a small cohort of digital sea urchin embryos to construct a prototypical representation of the cell lineage, which relates individual cell features with embryo-level dynamics. This multi-level data-driven probabilistic model relies on symmetries of the embryo and known cell types, which provide a generic coarse-grained level of observation for distributions of individual cell features. The prototype is defined as the centroid of the cohort in the corresponding statistical manifold. Among several results, we show that intra-individual variability is involved in the reproducibility of the developmental process. In the second part, we consider the mechanisms sources of variability during development and their relations to evolution. Building on experimental results showing variable phenotypic expression and incomplete penetrance in a zebrafish mutant line, we propose a clarification of the various levels of biological variability using a formal analogy with quantum mechanics mathematical framework. Surprisingly, we find a formal analogy between quantum entanglement and Mendel’s idealized scheme of inheritance. In the third part, we study biological organization and its relations to developmental paths. By adapting the tools of algebraic topology, we compute invariants of the network of cellular contacts extracted from confocal microscopy images of epithelia from different species and genetic backgrounds. In particular, we show the influence of individual histories on the spatial distribution of cells in epithelial tissues., Nous proposons dans cette thèse de caractériser quantitativement la variabilité à différentes échelles au cours de l'embryogenèse. Pour ce faire, nous utilisons une combinaison de modèles mathématiques et de résultats expérimentaux. Dans la première partie, nous utilisons une petite cohorte d'oursins digitaux pour construire une représentation prototypique du lignage cellulaire, reliant les caractéristiques des cellules individuelles avec les dynamiques à l'échelle de l'embryon tout entier. Ce modèle probabiliste multi-niveau et empirique repose sur les symétries des embryons et sur les identités cellulaires; cela permet d'identifier un niveau de granularité générique pour observer les distributions de caractéristiques cellulaires individuelles. Le prototype est défini comme le barycentre de la cohorte dans la variété statistique correspondante. Parmi plusieurs résultats, nous montrons que la variabilité intra-individuelle est impliquée dans la reproductibilité du développement embryonnaire. Dans la seconde partie, nous considérons les mécanismes sources de variabilité au cours du développement et leurs relations à l'évolution. En nous appuyant sur des résultats expérimentaux montrant une pénétrance incomplète et une expressivité variable de phénotype dans une lignée mutante du poisson zèbre, nous proposons une clarification des différents niveaux de variabilité biologique reposant sur une analogie formelle avec le cadre mathématique de la mécanique quantique. Nous trouvons notamment une analogie formelle entre l'intrication quantique et le schéma Mendélien de transmission héréditaire. Dans la troisième partie, nous étudions l'organisation biologique et ses relations aux trajectoires développementales. En adaptant les outils de la topologie algébrique, nous caractérisons des invariants du réseaux de contacts cellulaires extrait d'images de microscopie confocale d'épithéliums de différentes espèces et de différents fonds génétiques. En particulier, nous montrons l'influence des histoires individuelles sur la distribution spatiales des cellules dans un tissu épithélial.

National audience; In this article the homology of simploidal sets is studied. Simploidal sets generalize both simplicial complexes and cubical complexes, more precisely cells of simploidal sets are Cartesian products of simplices. We define one homology for simploidal sets and we prove in a combinatorial way that this homology is equivalent to the homology usually defined on simplicial structures.

Massive amounts of data are now available for study. Asking questions that are both relevant and possible to answer is a difficult task. One can look for something different than the answer to a precise question. Topological data analysis looks for structure in point cloud data, which can be informative by itself but can also provide directions for further questioning. A common challenge faced in this area is the choice of the right scale at which to process the data.One widely used tool in this domain is persistent homology. By processing the data at all scales, it does not rely on a particular choice of scale. Moreover, its stability properties provide a natural way to go from discrete data to an underlying continuous structure. Finally, it can be combined with other tools, like the distance to a measure, which allows to handle noise that are unbounded. The main caveat of this approach is its high complexity.In this thesis, we will introduce topological data analysis and persistent homology, then show how to use approximation to reduce the computational complexity. We provide an approximation scheme to the distance to a measure and a sparsifying method of weighted Vietoris-Rips complexes in order to approximate persistence diagrams with practical complexity. We detail the specific properties of these constructions.Persistent homology was previously shown to be of use for scalar field analysis. We provide a way to combine it with the distance to a measure in order to handle a wider class of noise, especially data with unbounded errors. Finally, we discuss interesting opportunities opened by these results to study data where parts are missing or erroneous.; La quantité de données disponibles n'a jamais été aussi grande. Se poser les bonnes questions, c'est-à-dire des questions qui soient à la fois pertinentes et dont la réponse est accessible est difficile. L'analyse topologique de données tente de contourner le problème en ne posant pas une question trop précise mais en recherchant une structure sous-jacente aux données. Une telle structure est intéressante en soi mais elle peut également guider le questionnement de l'analyste et le diriger vers des questions pertinentes. Un des outils les plus utilisés dans ce domaine est l'homologie persistante. Analysant les données à toutes les échelles simultanément, la persistance permet d'éviter le choix d'une échelle particulière. De plus, ses propriétés de stabilité fournissent une manière naturelle pour passer de données discrètes à des objets continus. Cependant, l'homologie persistante se heurte à deux obstacles. Sa construction se heurte généralement à une trop large taille des structures de données pour le travail en grandes dimensions et sa robustesse ne s'étend pas au bruit aberrant, c'est-à-dire à la présence de points non corrélés avec la structure sous-jacente.Dans cette thèse, je pars de ces deux constatations et m'applique tout d'abord à rendre le calcul de l'homologie persistante robuste au bruit aberrant par l'utilisation de la distance à la mesure. Utilisant une approximation du calcul de l'homologie persistante pour la distance à la mesure, je fournis un algorithme complet permettant d'utiliser l'homologie persistante pour l'analyse topologique de données de petite dimension intrinsèque mais pouvant être plongées dans des espaces de grande dimension. Précédemment, l'homologie persistante a également été utilisée pour analyser des champs scalaires. Ici encore, le problème du bruit aberrant limitait son utilisation et je propose une méthode dérivée de l'utilisation de la distance à la mesure afin d'obtenir une robustesse au bruit aberrant. Cela passe par l'introduction de nouvelles conditions de bruit et l'utilisation d'un nouvel opérateur de régression. Ces deux objets font l'objet d'une étude spécifique. Le travail réalisé au cours de cette thèse permet maintenant d'utiliser l'homologie persistante dans des cas d'applications réelles en grandes dimensions, que ce soit pour l'inférence topologique ou l'analyse de champs scalaires.

International audience

In his 1966's paper "Ktheory and Reality", Atiyah introduced a variant of Ktheory of complex vector bundles called KRtheory, which, in some sense, is a mixture of complex Ktheory KU, real Ktheory (also called orthogonal Ktheory) KO, and Anderson's selfconjugate Ktheory KSc. The main purpose of this thesis is to generalize that theory to the noncommutative framework of twisted groupoid Ktheory. We then introduce twisted groupoid KRtheory by using the powerful machineries of Kasparov's "real" KKtheory. Specifically, we deal with the Ktheory of graded C*algebras associated with groupoid dynamical systems endowed with involutions. Such dynamical systems are classified by the Real graded Brauer group to be defined and computed in terms of Cech cohomology classes. In this new Ktheory, we give the analogues of the fundamental results in Ktheory such as the MayerVietoris exact sequences, the Bott periodicity and the Thom isomorphism theorem, Dans son article de 1966 intitulé "Ktheory and Reality", Atiyah introduit une variante de la Kthéorie des fibres vectoriels complexes, notée KR, qui, d'une certaine manière, englobe à la fois la Ktheory complexe KU, la Ktheory réelle KO (dite aussi orthogonale), et la Kthéorie autoconjuguée KSc d'Anderson. Dans cette thèse, nous généralisons cette théorie au cadre noncommutatif de la Kthéorie tordue des groupoïdes topologiques. Nous développons ainsi la KRthéorie tordue des groupoïdes en nous servant principalement des outils de la KKthéorie "réelle" de Kasparov. Il s'agit notamment de l'étude de la Kthéorie des C*algèbres graduées associées à des systèmes dynamiques de groupoides munis de certaines involutions. Les classes d'équivalence de tels systèmes composent le groupe de Brauer Réel gradué que nous définissons et calculons en termes de classes de cohomologie de Cech. Nous donnons dans cette nouvelle théorie les analogues des résultats classiques en Kthéorie tels que les suites exactes de MayerVietoris, la périodicité de Bott et le théorème d'isomorphisme de Thom

Cette version inclut le code source du programme Bianchi.gp, qui a été développé pour cette thèse. Il se trouve dans les fichiers "ANNEX".; This thesis consists of the study of the geometry of a certain class of arithmetic groups, by means of a proper action on a contractible space. We will explicitly compute their group homology, and their equivariant K-homology. More precisely, consider an imaginary quadratic number field, and its ring of integers R. The Bianchi groups are the groups SL_2(R) and PSL_2(R). These groups act in a natural way on hyperbolic three-space. The Bianchi groups are a key to the study of a larger class of groups, the Kleinian groups, which dates back to works of Poincaré. In fact, each non-cocompact arithmetic Kleinian group is commensurable with some Bianchi group. The author has implemented the computation of a fundamental domain for the Bianchi groups. By computing the stabilisers and identifications on this fundamental domain, we obtain an explicit orbifold structure. We use it to study different aspects of the geometry of our groups. Firstly, we compute group homology with integer coefficients, using the equivariant Leray/Serre spectral sequence. Secondly, we compute the Bredon homology of the Bianchi groups, from which we deduce their equivariant K-homology. By the Baum/Connes conjecture, which is verified by the Bianchi groups, we obtain the K-theory of the reduced C*-algebras of the Bianchi groups, as isomorphic images. Finally, we complexify our orbifolds, by complexifying the real hyperbolic three-space. We obtain orbifolds given by the induced action of the Bianchi groups on complex hyperbolic three-space. Then we compute the Chen/Ruan orbifold cohomology for these complex orbifolds. This is one side of Ruan's cohomological crepant resolution conjecture.; Cette thèse consiste d'une étude de la géométrie d'une certaine classe de groupes arithmétiques, à travers d'une action propre sur un espace contractile. Nous calculons explicitement leur homologie de groupe, et leur K-homologie équivariante. Plus précisément, considérons un corps de nombres quadratique imaginaire et son anneau d'entiers A. Les groupes de Bianchi sont les groupes SL_2(A) et PSL_2(A). Ces groupes agissent d'une manière naturelle sur l'espace hyperbolique à 3 dimensions. Ils constituent une clef pour l'étude d'une classe plus large de groupes, les groupes Kleiniens, étudiés depuis Poincaré. En fait, chaque groupe Kleinien arithmétique non-cocompact est commensurable avec un des groupes de Bianchi. L'auteur a implémenté à l'ordinateur, le calcul d'un domaine fondamental pour ces groupes. En calculant les stabilisateurs et identifications sur ce domaine fondamental, nous obtenons une structure explicite d'orbi-espace. Nous nous en servons pour étudier des aspects différents de la géométrie des groupes de Bianchi. D'abord, nous calculons l'homologie de groupe à coefficients entiers, à l'aide de la suite spectrale équivariante de Leray/Serre. Ensuite, nous calculons l'homologie de Bredon de groupes de Bianchi, de laquelle nous déduisons leur K-homologie équivariante. Par la conjecture de Baum/Connes, qui est vérifiée par nos groupes, nous obtenons la K-théorie des C*-algèbres réduites de nos groupes. Finalement, nous complexifions nos orbi-espaces, en complexifiant l'espace hyperbolique. Ceci nous permet de calculer la cohomologie d'orbi-espace de Chen/Ruan, qui est l'un des deux côtés de la conjecture de la résolution cohomologique crépante de Ruan.

Il s'agit d'une thèse d'histoire des mathématiques.; The goal of this thesis is the historical study of the genesis of group cohomology, a theory that came up during the nineteen-forties. It is an algebraic theory in the sense that it gives results on groups and it is as well a topologic one because of the methods it involves. The present work analyses how topology and algebra interpenetrated each other to give birth to this abstract and elaborate theory, by putting into perspective this phenomenon with respect to more global ones like the birth and the rise of modern algebra. Namely we discuss the influence of Emmy Noether in the algebraization of topology and the respective motivations of Heinz Hopf and Eilenberg & Mac Lane that led them to the development of group homology. A meticulous analysis of several seminal articles - due to the authors cited above and others including Schur, Vietoris and Eckmann - enables to highlight the fact that the will to answer specific mathematical problems was perhaps more propulsive in the emergence of this architectonic theory that group cohomology is, than great guiding ideas elaborated in the framework of structural representations of mathematics.; Cette thèse étudie d'un point de vue historique la genèse de la cohomologie des groupes, théorie qui vit le jour dans les années 1940. Il s'agit d'une théorie à la fois algébrique, au sens où elle donne des résultats sur les groupes, et topologique par les méthodes qu'elle met en œuvre . Le présent travail analyse les mécanismes par lesquels la topologie et l'algèbre se sont interpénétrées pour donner naissance à cette théorie abstraite et élaborée, en mettant notamment en perspective ce phénomène par rapport à ceux, plus globaux, de la naissance et de l'expansion de l'algèbre moderne. Y sont notamment discutées l'influence d'Emmy Noether dans l'algébrisation de la topologie et les motivations respectives de Heinz Hopf et d'Eilenberg & Mac Lane les ayant menés à l'élaboration de l'homologie des groupes. L'analyse minutieuse de plusieurs articles phares - dus aux auteurs cités précédemment mais aussi à Schur, Vietoris ou encore Eckmann - permet de mettre en lumière le fait que la volonté de répondre à des problèmes mathématiques précis fut peut-être plus motrice, dans l'émergence de cette théorie architectonique qu'est la cohomologie des groupes, que de grandes idées directrices conçues au sein de représentations structurales des mathématiques.

Leafwise Dolbeault cohomology measures the obstruction to solve the -problem along the leaves of a complex foliation. We compute this cohomology using essentially methods of cohomology of groups for some interesting examples : 1) a complex one dimensional linear foliation on the torus Tⁿ ; 2) a submersion whose fibres are elliptic curves ; 3) the two dimensional complex affine Reeb foliation on the Hopf manifold S4x S1 ; 4) the complex foliation on the hyperbolic torus obtained by a locally free action of the real affine Lie group where A∈SL (n,Z) is a hyperbolic and diagonalizable matrix whose eigenvalues are positive real numbers., La cohomologie de Dolbeault feuilletée mesure l’obstruction à la résolution du problème du dbarre (ou delta-barre) le long des feuilles d’un feuilletage complexe. Dans ce travail, on étudie cette cohomologie en utilisant (le plus souvent) des méthodes de cohomologie de groupes discrets sur certains exemples assez significatifs : 1) un feuilletage complexe linéaire de dimension 1 sur le tore Tⁿ ; 2) une submersion en courbes elliptiques ; 3) le feuilletage complexe affine (de Reeb) de dimension 2 sur la variété de Hopf Sexposant4x S¹ ; 4) le feuilletage complexe sur le tore hyperbolique Texposant n+1 indice A obtenu par une action localement libre du groupe affine réel (groupe de Lie des transformations affines qui préservent la droite réelle) où A∈SL (n,Z) est hyperbolique diagonalisable ayant toutes ses valeurs propres réelles positives.

Leafwise Dolbeault cohomology measures the obstruction to solve the -problem along the leaves of a complex foliation. We compute this cohomology using essentially methods of cohomology of groups for some interesting examples : 1) a complex one dimensional linear foliation on the torus Tⁿ ; 2) a submersion whose fibres are elliptic curves ; 3) the two dimensional complex affine Reeb foliation on the Hopf manifold S4x S1 ; 4) the complex foliation on the hyperbolic torus obtained by a locally free action of the real affine Lie group where A∈SL (n,Z) is a hyperbolic and diagonalizable matrix whose eigenvalues are positive real numbers.; La cohomologie de Dolbeault feuilletée mesure l’obstruction à la résolution du problème du dbarre (ou delta-barre) le long des feuilles d’un feuilletage complexe. Dans ce travail, on étudie cette cohomologie en utilisant (le plus souvent) des méthodes de cohomologie de groupes discrets sur certains exemples assez significatifs : 1) un feuilletage complexe linéaire de dimension 1 sur le tore Tⁿ ; 2) une submersion en courbes elliptiques ; 3) le feuilletage complexe affine (de Reeb) de dimension 2 sur la variété de Hopf Sexposant4x S¹ ; 4) le feuilletage complexe sur le tore hyperbolique Texposant n+1 indice A obtenu par une action localement libre du groupe affine réel (groupe de Lie des transformations affines qui préservent la droite réelle) où A∈SL (n,Z) est hyperbolique diagonalisable ayant toutes ses valeurs propres réelles positives.

D'un point de vue rationnel, la question fondamentale dans l'étude des espaces de configurations dans une variété est la suivante : " Le type d'homotopie rationnel de l'espace des configurations de k points d'une variété simplement connexe dépend-t-il uniquement du type d'homotopie rationnel de cette variété ? " Dans cet ouvrage, nous nous intéressons aux variétés compactes, simplement connexes et sans bord. Dans ce cadre précis, nous étudions le lien entre les invariants d'homotopie rationnelle de l'espace des configurations de 2 points dans une variété, et le modèle minimal de Sullivan de cette variété. Le point clef de ce travail est la construction explicite d'une algèbre de Sullivan minimale qui s'injecte dans le modèle minimal de Sullivan de l'espace des configurations de deux points d'une variété. Nous en déduisons deux résultats essentiels concernant l'algèbre de Lie d'homotopie rationnelle de cet espace. D'une part, nous identifions une relation de cette algèbre de Lie, induite par l'action du groupe des permutations de deux éléments sur l'espace des configurations de deux points. D'autre part, nous prouvons que si la variété est coformelle et de catégorie rationnelle supérieure à 3, alors cette algèbre de Lie est complètement déterminée par le modèle minimal de la variété. (MATH 3)--UCL, 2006

Nous proposons deux énoncés beaucoup plus fort que la conjecture de Hadwiger. Ils sont l'avantage d'être maniables et accessibles au raisonnement par récurrence plus facilement. Il peut être intéressant aussi de leur chercher des contre-exemples.

In a distributed application, high-availability of a critical online service is ensured despite failures by duplicating the vital components of the server. Whilst guaranteeing the access to the server at all times, duplication requires particular care, so as to maintain a consistent state amongst all components. A distributed computation plays a key-role in preserving the consistency of the state in this case. Indeed, one of the fundamental forms of distributed computation is distributed agreement. In a distributed agreement problem, the components of the system, called processes, are supposed to all propose a value and eventually decide on a common value that depends on the proposed values. Designing correct distributed agreement algorithms relies on a mathematical model abstracting the details of the underlying physical model. In practice, there are many models, inspired from various types of physical failures. Coping with one type of failures rather than another one, for a distributed agreement algorithm, is not of equal difficulty. Indeed some types are intrinsically harder to cope with than other ones. The thesis studies how distributed algorithms can be transformed from one model to another one. The idea is to design distributed agreement algorithms in models in which the task is made as easiest and least error-prone as possible, and execute the transformed algorithms in models imposed by the underlying physical constraints. We investigate another aspect of transforming distributed computations, the notion of reducibility amongst distributed computations. Reducibility offers an elegant way for deducing lower or upper bounds on the complexity of a distributed algorithm from complexity bounds that have been proved elsewhere, about a different distributed computation or in a different model. For investigating reducibility, the thesis considers two very general classes of models: synchronous models, in which the communication delay and the process execution speed are known and bounded, and asynchronous models, in which the communication delay and the process execution speed are unknown and potentially unbounded. The thesis investigates reducibility of a distributed agreement problem called set agreement. Precisely, we consider the early-deciding variant of set agreement, in which processes must decide as fast as they can in any execution. We prove a lower bound on the complexity of early-deciding set agreement in the synchronous model. The proof works by reducing the impossibility of set agreement in the asynchronous model to the desired lower bound. In some cases, complexity bounds must still be derived with ad-hoc arguments, for example when there is no apparent connection with existing results. The thesis presents an alternative approach to reducibility, namely the connection of distributed computing with algebraic topology. Within this framework, we derive a lower bound for the complexity of early-deciding set agreement in the synchronous model. For all the lower bounds that we derive in the thesis, we show that these bounds are tight, by presenting for each lower bound an algorithm matching the complexity of the lower bound.