Cette thèse a pour objet de développer de nouveaux algorithmes pour les groupes de tresses. Un problème important en théorie mathématique des tresses est d'améliorer les algorithmes existants pour résoudre le problème de conjugaison. Nous résolvons complètement ce problème dans le cas du groupe des tresses à quatre brins, en exhibant un algorithme de complexité cubique en terme de la longueur des entrées. La démonstration s'appuie sur deux aspects fondamentaux des groupes de tresses : la structure de groupe de Garside et la structure de groupe de difféotopie. Comme résultat préliminaire, nous développons un algorithme de complexité quadratique capable de classifier les tresses à quatre brins selon leur type de Nielsen-Thurston. Plus généralement, nous étudions ce problème de classification pour un nombre arbitraire de brins. Nous donnons une adaptation des résultats connus de Benardete-Gutiérrez-Nitecki au cadre de la structure de Garside duale. Enfin, à l'aide d'un résultat profond (et non constructif) de Masur-Minsky, nous prouvons l'existence d'un algorithme de complexité polynômiale pour décider le type de Nielsen-Thurston d'une tresse avec un nombre de brins arbitraire.

Étant donné un complexe de groupes, quand peut-on déduire une propriété de son groupe fondamental à partir des propriétés analogues de ses groupes locaux ? Ce problème naturel de géométrie des groupes a fait l'objet de nombreux travaux dans le cas des graphes de groupes et des complexes de groupes finis. Cette thèse se propose de développer des outils géométriques pour étudier le cas des complexes de groupes à courbure négative ou nulle. Nous nous intéressons à des propriétés de nature asymptotique : EZ-structures, hyperbolicité. Ce faisant, nous démontrons un théorème de combinaison pour les groupes hyperboliques qui généralise au complexe de groupes de dimension arbitraire un théorème de Bestvina-Feighn.

La classification des groupes simples finies achevée en 2004 par Aschbacher et Smith au terme de décennies de travaux par des centaines de mathématiciens livre 18 familles infinies et 26 groupes appelés sporadiques. Ces derniers sont dotés de propriétés singulières. Dans ma thèse de doctorat, nous étudions le groupe sporadique de O'Nan -- usuellement dénoté O'N -- d'un point de vue géométrique, dans la lignée des travaux des Professeurs Buekenhout, Dehon et Leemans.<p><p>Nous abordons essentiellement quatre facettes de la géométrie de O'N. Tout d'abord, nous produisons la classification complète des géométries Buekenhout--Cara--Dehon--Leemans (BCDL) de O'N, une tâche commencée par Leemans en 2010. Les géomé-tries BCDL sont caractérisées par des axiomes inspirés de la Théorie des Immeubles de Jacques Tits. La majorité des groupes simples finis sont caractérisés par un immeuble et un diagramme. Parmi les exceptions se trouvent les groupes sporadiques. Une géométrie BCDL est plus générale qu'un immeuble, mais s'en rapproche.<p><p>Ensuite, nous étudions une géométrie pour le groupe d'automorphismes de O'N construite à partir de paires d'involutions commutantes. Les involutions jouent un rôle majeur dans la théorie des groupes simples finis. Ces travaux sont inspirés de la construction d'une tour de géométries pour les groupes de Fischer construite à partir de paires d'involutions commutantes due à Buekenhout.<p><p>Nous poursuivons en étudiant les polytopes abstraits réguliers sur lesquels O'N agit. Nous produisons la classification des polytopes de rang maximum, à savoir 4.<p><p>Enfin, nous étudions O'N sous le spectre des cartes régulières. Tout polyèdre abstrait régulier est une carte régulière, mais la réciproque n'est pas vraie. Nous donnons un algorithme permettant d'énumérer par type les cartes régulières pour un groupe fini donné. Ceci nous permet de borner le nombre de polyèdres abstraits réguliers sur lesquels O'N agit.<p><p>Nous produisons également les treillis de sous-groupes de O'N et de son groupe d'automorphismes. / Doctorat en Sciences / info:eu-repo/semantics/nonPublished

Le but de cette thèse est de fournir une caractérisation topologique de tresses virtuelles. Les tresses virtuelles sont des classes d’équivalence de diagrammes de type tresses tracés sur le plan. La relation d’équivalence est générée par l’isotopie, les mouvements de Reidemeister et les mouvements de Reidemeister virtuels. L’ensemble des tresses virtuelles est munie d’une opération de groupe. On parlera alors du groupe de tresses virtuelles. Dans le Chapitre 1, nous introduisons les notions de base de la théorie de noeuds virtuels, nous évoquons certains propriétés du groupe tresses virtuelles, et des liens qu’il a avec le groupe de tresses classiques. Dans le Chapitre 2, nous introduisons la notion de diagramme de Gauss tressé (ou diagramme de Gauss horizontal), et on démontre qu’il s’agit là d’une bonne réinterprétation combinatoire pour les tresses virtuelles. On généralise en particulier certains résultats connus en théorie de noeuds virtuels. Un application est de retrouver la présentation classique du groupe de tresses virtuelles pures à l’aide des diagrammes de Gauss tressés. Dans le Chapitre 3, on introduit les tresses abstraites et on montre qu’elles sont en correspondance bijective avec les tresses virtuelles. Les tresses abstraites sont des classes d’équivalence des diagrammes de type tresses tracés sur une surface orientable avec deux composantes de bord. La relation d’équivalence est générée par l’isotopie, la compatibilité, la stabilité et les mouvements de Reidemeister. La compatibilité est la relation d’équivalence générée par les difféomorphismes préservant l’orientation. La stabilité est la relation d’équivalence générée par l’addition ou la suppression d’anses à la surface, dans le complémentaire du diagramme. Dans le Chapitre 4, on démontre que tout tresse abstraite admets une unique représentant de genre minimal, à compatibilité et mouvements de Reidemeister prés. En particulier, les tresses classiques se plongent dans les tresses abstraites. / The purpose of this thesis is to give a topological characterization of virtual braids. Virtual braids are equivalence classes of planar braid-like diagrams identified up to isotopy, Reidemeister and virtual Reidemeister moves. The set of virtual braids admits a group structure and is called the virtual braid group. In Chapter 1 we present a general introduction to the theory of virtual knots, and we discuss some properties of virtual braids and their relations with classical braids. In Chapter 2 we introduce braid-Gauss dia- grams, and we prove that they are a good combinatorial reinterpretation of virtual braids. In particular this generalizes some results known in virtual knot theory. As an application, we use braid-Gauss diagrams to recover a well known presentation of the pure virtual braid group. In Chapter 3 we introduce abstract braids and we prove that they are in a bijective cor- respondence with virtual braids. Abstract braids are equivalence classes of braid-like diagrams on an orientable surface with two boundary components. The equivalence relation is generated by isotopy, compatibility, stability and Reidemeister moves. Compatibility is the equivalence relation generated by orientation preserving diffeomorphisms. Stability is the equivalence relation generated by adding handles to or deleting handles from the surface in the complement of the braid-like diagram. In Chapter 4 we prove that for any abstract braid, there is a unique representative of minimal genus, up to compatibility and Reidemeister equivalence. In particular this implies that classical braids embed in abstract braids.

Dans le développement logiciel en industrie, les documents de spécification jouent un rôle important pour la communication entre les analystes et les développeurs. Cependant, avec le temps, les changements de personel et les échéances toujours plus courtes, ces documents sont souvent obsolètes ou incohérents avec l'état effectif du système, i.e., son code source. Pourtant, il est nécessaire que les composants du système logiciel soient conservés à jour et cohérents avec leurs documents de spécifications pour faciliter leur développement et maintenance et, ainsi, pour en réduire les coûts. Maintenir la cohérence entre spécification et code source nécessite de pouvoir représenter les changements sur les uns et les autres et de pouvoir appliquer ces changements de manière cohérente et automatique. Nous proposons une solution permettant de décrire une représentation d'un logiciel ainsi qu'un formalisme mathématique permettant de décrire et de manipuler l'évolution des composants de ces représentations. Le formalisme est basé sur les triplets de Hoare pour représenter les transformations et sur la théorie des groupes et des homomorphismes de groupes pour manipuler ces transformations et permettrent leur application sur les différentes représentations du système. Nous illustrons notre formalisme sur deux représentations d'un système logiciel : PADL, une représentation architecturale de haut niveau (semblable à UML), et JCT, un arbre de syntaxe abstrait basé sur Java. Nous définissons également des transformations représentant l'évolution de ces représentations et la transposition permettant de reporter les transformations d'une représentation sur l'autre. Enfin, nous avons développé et décrivons brièvement une implémentation de notre illustration, un plugiciel pour l'IDE Eclipse détectant les transformations effectuées sur le code par les développeurs et un générateur de code pour l'intégration de nouvelles représentations dans l'implémentation. / When developing software system in industry, system specifications are heavily used in communication among analysts and developers. However, system evolution, employee turn-over and shorter deadlines lead those documents either not to be up-to-date or not to be consistent with the actual system source code. Yet, having up-to-date documents would greatly help analysts and developers and reduce development and maintenance costs. Therefore, we need to keep those documents up-to-date and consistent. We propose a novel mathematical formalism to describe and manipulate the evolution of these documents. The mathematical formalism is based on Hoare triple to represent the transformations and group theory and groups homomorphisms to manipulate these transformations and apply them on different representations. We illustrate our formalism using two representation of a same system: PADL, that is an abstract design specification (similar to UML), and JCT, that is an Abstract Syntax Tree for Java. We also define transformations describing their evolutions, and transformations transposition from one representation to another. Finally, we provide an implementation of our illustration, a plugin for the Eclipse IDE detecting source code transformations made by a developer and a source code generator for integrating new representations in the implementation.

Nous étudions dans cette thèse le roulement sans glissement et sans pivotement de deux variétés lisses M et Ṁ l'une sur l'autre de dimensions et n et ṅ respectivement. L'objectif principal est de chercher des conditions nécessaires et suffisantes de la commandabilité du système commandé défini par le roulement. Dans le premier chapitre, on présente les motivations et le plan de la thèse ainsi les notations utilisées le long des chapitres. Dans le deuxième chapitre, on caractérise l'espace d'état du roulement quand M et Ṁ sont des variétés Riemanniennes lorsque n n'est pas nécessairement égal à ṅ et du développement quand M et Ṁ sont des variétés affines munies des connexions affines avec n = ṅ Ainsi, on donne les relèvements et les distributions correspondant aux deux notions précédentes. Le troisième chapitre contient quelques résultats de la commandabilité du système de roulement des variétés Riemanniennes. Plus précisément, on présente les conditions nécessaires de la non-commandabilité du roulement d'une variété Riemannienne 3-dimensionnelle sur une autre 2-dimensionnelle.Le chapitre 4 porte sur le roulement d'une variété Riemannienne de dimension 2 sur une autre de dimension 3. On trouve que la dimension d'une orbite non-ouverte quelconque de l'espace d'état appartient à {2,5,6,7}. Les aspects géométriques de deux variétés sont liés principalement avec le fait que la variété de dimension 3 contient une sous-variété totalement géodésique de dimension 2.Dans le dernier chapitre, on introduit et étudie un concept d'holonomie horizontale associé à un triplet (M,∇,Δ ) avec M variété différentielle connexe, ∇ connection affine complète sur M et Δ distribution complètement commandable. Si H^∇est le groupe d'holonomie associé à Ṁ on considère alors son sous-groupe obtenu uniquement en considérant le transport ∇- parallèle par rapport aux lacets dans M tangents à la distribution Δ On le note H_Δ^∇et on l’appelle groupe d'holonomie horizontal. On prouve que le groupe d'holonomie horizontal H_Δ^∇ est un sous-groupe de Lie de GL(n). Puis, on démontre par un exemple que la fermeture du groupe d'holonomie horizontal restreint (H_Δ^∇ )^0 n'est pas nécessairement égal à H_Δ^∇. A cette fin, on utilise le modèle du roulement avec M un groupe de Carnot homogène munie d'une connexion de Levi-Civita associée à une métrique Riemannienne sur l'espace Euclidien R^n munie de la connexion Euclidienne. / In this thesis, we study the rolling motion without spinning nor slipping of a smooth manifolds M and Ṁ against another of dimensions n and ṅ respectively. The purpose is to find the necessary and sufficient conditions for the controllability issue of the system of rolling. We start by a French review of the principal results of the thesis is included in the introduction. In Chapter 1, we present the motivations of the subject thesis, the structure of the contents and the notations used along the manuscript. The second chapter contain a characterization of the state space of rolling manifolds when M and Ṁ are Riemannian manifolds with n and ṅ are not necessarily equal and of the development of manifolds when M and Ṁ are affine manifolds of dimension n = ṅ equipped with affine connections. We also state the definitions of the lifts and the distributions with respect to the previous notions. The controllability results of the rolling system of Riemannian manifolds is included in Chapter 3. We give all the necessary conditions of the non-controllability of rolling of 3-dimensional Riemannian manifold against 2-dimensional Riemannian manifold. Chapter 4 deals with the rolling of a 2-dimensional Riemannian manifold against a 3-dimensional Riemannian manifold. We prove that the dimension of an arbitrary non-open orbit of the state space belongs to {2,5,6,7}. The geometrical aspects of the two manifolds depend on the existence of a 2-dimensional totally geodesic submanifold in the 3-dimensional manifold. The last chapter introduces and addresses the issue of horizontal holonomy associated to a triple (M,∇,Δ) with M smooth connected manifold, ∇ complete affine connection M and Δ completely controlable distribution over M. If H_Δ^∇. denotes the holonomy group associated with (M,∇) one considers its subgroup obtained by considering only the ∇- parallel transport with respect to loops of M tangent to the distribution Δ This subgroup is denoted by H_Δ^∇ and we call it horizontal holonomy group. We prove that the horizontal holonomy group H_Δ^∇ is a Lie subgroup of GL(n). Then, we show by means of an example that the closure of a restricted horizontal holonomy group on a Riemannian manifold is not necessarily equal to the holonomy group of the Riemannian manifold. To this end, we use the rolling problem of M taken as a step 2 homogeneous Carnot group equipped with the Levi-Civita connection associated to a Riemannian metric onto the Euclidean space R^n equipped with the Euclidean connection.

Dans cette thèse, nous utilisons et contribuons à la théorie des produits de matrices aléatoires afin d'étudier des propriétés génériques des éléments et des sous-groupes des groupes linéaires. Notre premier résultat donne une version probabiliste de l'alternative de Tits : nous montrons que si M_n et M'_n sont deux marches aléatoires indépendantes sur un groupe linéaire de type fini non virtuellement résoluble alors presque sûrement les deux marches finiront par engendrer un sous-groupe libre non abélien à deux générateurs. Cela répond par l'affirmative à une question de Guivarc'h et de Gilman, Miasnikov et Osin. Plus précisément, nous montrons que la probabilité que M_n et M'_n n'engendrent pas un sous-groupe libre décroit exponentiellement vite vers zéro. Notre outil principal est la théorie des produits de matrices aléatoires. Durant la preuve, nous établissons de nouveaux théorèmes limites dans cette théorie, d'une part en généralisant des résultats connus dans le cadre des produits de matrices à valeurs dans les corps archimédiens à tout corps local, d'autre part en donnant des résultats qui sont nouveaux même sur R. Par exemple, nous montrons que sous des hypothèses naturelles sur la marche aléatoire, les composantes suivant K de M_n dans la décomposition KAK deviennent asymptotiquement indépendantes avec vitesse exponentielle. Dans la deuxième partie de la thèse, nous utilisons ces résultats pour étudier la transience des sous-variétés des groupes algébriques. Un de nos résultats peut être formulé comme suit: soient H un sous-groupe non élémentaire de SL_2(R), une probabilité adaptée sur H ayant un moment exponentiel, alors pour toute sous-variété algébrique propre V de SL_2(R), la probabilité que la marche aléatoire appartienne à V décroit exponentiellement vite vers zéro. Par conséquent, la sous-variété algébrique V est transiente pour la marche aléatoire. Nous généralisons cet énoncé au cas ou la marche aléatoire est adaptée sur un groupe Zariski dense des points réels d'un groupe algébrique défini et déployé sur R. Ces résultats sont à comparer avec des travaux récents de Kowalski et de Rivin. / In this thesis, we use and contribute to the theory of random matrix products in order to study generic properties of elements and subgroups of linear groups. Our first result gives a probabilistic version of the Tits alternative : we show that two independent random walks M_n and M'_n on a non virtually solvable finitely generated linear group will eventually generate a non abelian free subgroup. This answers a question of Guivarc'h and Gilman, Miasnikov and Osin. We show in fact that the probability that M_n and M'_n do not generate a free subgroup decreases exponentially fast to zero. Our methods rely deeply on random matrix products theory. During the proof we give some new limit theorems concerning this theory, some of them will be the generalization of known results for matrices taking value in archimedean fields to arbitrary local fields, others will be new even over R. For example, we show that under natural assumptions on the random walk, the K-parts of M_n in the KAK decomposition become asymptotically independent with exponential speed. Next, we use these properties to study the transience of algebraic subvarieties in algebraic groups. One of our results can be formulated as follows: let H be a non elementary subgroup of SL_2(R), a probability measure with an exponential moment whose support generates H, then for every proper algebraic subvariety V of SL_2(R), the probability that the random walk lies in V decreases exponentially fast to zero. This shows that every proper algebraic subvariety is transient for the random walk. We generalize this result to the case where the support of the probability measure generates a Zariski dense subgroup of the real points of an algebraic group defined and split over R. These results share common flavor with recent works of Kowalski and Rivin

L'étude du système Ce-Ni-Ge a permis d'établir une corrélation étroite entre les propriétés physiques de ces germaniures (gouvernées par l'état fondamental du cérium résultant d'une compétition entre deux types d'interactions : effet Kondo et interaction magnétique de type RKKY) et leur composition chimique. Ainsi, au sein du diagramme de phase ternaire Ce-Ni-Ge, nous avons établi que: (i) les germaniures riches en Ni sont soit des composés de valence intermédiaire (CeNiGe, Ce3Ni4Ge4 et CeNi4.25Ge0.75), soit des systèmes "fermions lourds" (CeNi2Ge2 et CeNi9Ge4). Notons que pour la séquence CeNi2Ge2 → Ce3Ni4Ge4 → CeNiGe, le caractère de valence intermédiaire est de plus en plus marqué; (ii) les germaniures les plus riches en Ge (>50 % atomique) sont antiferromagnétiques à basse température; dans ces composés (Ce2NiGe6, Ce3Ni2Ge7, CeNiGe3, Ce2Ni3Ge5 et CeNiGe2) l'ion cérium est trivalent; les structures magnétiques de ces composés ont été déterminées par diffraction neutronique, la valeur du moment magnétique de Ce3+ (ainsi que la température de Néel) diminue des composés les plus riches en Ge aux composés les moins riches en Ge (propriété associée à la force de l'effet Kondo).

Cette thèse est divisée en deux parties. La première partie concerne la commutation rapide des informations dans les réseaux ATM. Dans le chapitre 2, nous décrivons la technologie ATM. Dans le chapitre 3, nous modélisons le problème du positionnement des chemins virtuels et définissons les deux paramètres étudiés, charge et nombre de sauts d'un VPL. Nous discutons l'orientation du modèle, la complexité du problème, puis proposons une synthèse des résultats de la littérature. Les démonstrations des résultats originaux se trouvent dans les chapitres 4 et 5. La seconde partie concerne l'échange total dans les réseaux d'interconnexion entre processeurs. Dans le chapitre 6, nous introduisons les notions de théorie des groupes nécessaires ainsi que la motivation du problème. L'objet du chapitre 7 est de caractériser les graphes de Cayley admettant un certain automorphisme de graphe (appelé rotation complète) permettant de construire d'une manière simple un protocole d'échange total optimal. Nous mettons en évidence des conditions nécessaires sur le groupe pour que le graphe admette une rotation complète. Nous donnons la liste exhaustive des graphes de Cayley admettant une rotation complète parmi les graphes de Cayley engendrés par des transpositions.

L'objet de cette thèse est d'obtenir une description des plongements élémentaires (au sens de la logique du premier ordre) dans un groupe hyperbolique sans torsion. Le résultat principal décrit ces plongements en terme d'une structure définie par Sela dans sa solution au problème de Tarski: la structure de tour hyperbolique. Ainsi, si H est plongé élementairement dans un groupe hyperbolique sans torsion G, on peut obtenir G en amalgamant successivement des groupes de surfaces à bord à un produit libre de H avec des groupes libres et des groupes de surfaces sans bord. Ceci permet en corollaire de montrer qu'un sous-groupe plongé élémentairement dans un groupe libre de type fini est un facteur libre. Les techniques utilisées pour obtenir cette description sont essentiellement géométriques: actions sur des arbres réels ou simpliciaux, existence de décompositions JSJ. On s'appuie également sur des résultats d'existence d'ensembles de factorisation qui affirment que pour certains groupes A de type fini, étant donné un groupe hyperbolique sans torsion G, il existe un ensemble fini de quotients de A tel que tout morphisme non injectif de A vers G se factorise par l'un de ces quotients après précomposition par un automorphisme de A. On expose une preuve de ces résultats, y compris une version complète et détaillée du shortening argument de Rips et Sela. Le shortening argument montre, grâce à l'analyse de Rips des actions sur des arbres réels, que si une suite d'action d'un groupe A sur des espaces hyperboliques converge vers un A-arbre réel d'un certain type, alors une infinité de ces actions peuvent être raccourcies.