Deux groupes sont dits élémentairement équivalents s'ils satisfont les mêmes énoncés du premier ordre dans le langage des groupes. Aux environs de l'année 1945, Tarski posa la question suivante, connue désormais comme le problème de Tarski : les groupes libres non abéliens sont-ils élémentairement équivalents ? Une réponse positive à cette fameuse question fut apportée plus d'un demi-siècle plus tard par Sela, et en parallèle par Kharlampovich et Myasnikov, comme le point d'orgue de deux volumineuses séries de travaux. Dans la foulée, Sela généralisa aux groupes hyperboliques sans torsion, dont les groupes libres sont des représentants emblématiques, les méthodes de nature géométrique qu'il avait précédemment introduites à l'occasion de son travail sur le problème de Tarski. Les résultats rassemblés ici s'inscrivent dans cette lignée, en s'en démarquant toutefois dans la mesure où ils traitent des théories du premier ordre des groupes hyperboliques en présence de torsion. Dans un premier chapitre, on démontre, entre autres, que tout groupe de type fini qui est élémentairement équivalent à un groupe hyperbolique est lui-même hyperbolique. On démontre ensuite que les groupes virtuellement libres sont presque homogènes, ce qui signifie que deux éléments qui sont indiscernables du point de vue de la logique du premier ordre sont dans la même orbite sous l'action du groupes des automorphismes du groupe ambiant, à une indétermination finie près. Enfin, on donne une classification complète des groupes virtuellement libres de type fini du point de l'équivalence élémentaire à deux quantificateurs. / Two groups are said to be elementarily equivalent if they satisfy the same first-order sentences in the language of groups, that is the same mathematical statements whose variables are only interpreted as elements of a group. Around 1945, Tarski asked the following question : are non-abelian free groups elementarily equivalent? An affirmative answer to this famous Tarski's problem was given in 2006 by Sela and independently by Kharlampovich and Myasnikov, as the culmination of two voluminous series of papers. Then, Sela gave a classification of all finitely generated groups that are elementarily equivalent to a given torsion-free hyperbolic group. The results contained in the present thesis fall into this context and deal with first-order theories of hyperbolic groups with torsion. In the first chapter, we prove that any finitely generated group that is elementarily equivalent to a hyperbolic group is itself a hyperbolic group. Then, we prove that virtually free groups are almost homogeneous, meaning that elements are almost determined up to automorphism by their type, i.e. the first-order formulas they satisfy. In the last chapter, we give a complete classification of finitely generated virtually free groups up to elementary equivalence with two quantifiers.

Given a presentation of G, the word problem asks whether there exists an algorithm to determine which words in the free group, F(A), represent the identity in G. In this thesis, we study small cancellation theory, developed by Lyndon, Schupp, and Greendlinger in the mid-1960s, which contributed to the resurgence of geometric group theory. We investigate the connection between Van Kampen diagrams and the small cancellation hypotheses. Groups that have a presentation satisfying the small cancellation hypotheses C'(1/6), or C'(1/4) and T(4) have a nice solution to the word problem known as Dehn’s Algorithm.

<p>This thesis concerns itself with drawing out some interesting connections between the fields of group theory and formal language theory. Given a group with a finite set of generators, it is natural to consider the set of generators and their inverses as an alphabet. We can then consider formal languages such that every group element has at least one representative in the language. We examine what the structure of the language can tell us about group theoretic properties, focusing on the word problem, automatic structures on groups, and generalizations of automatic structures. Finally we prove new results concerning applications of languages of nested words for studying the word problem.</p> / Master of Science (MSc)

Dans cette thèse, nous nous intéressons à diverses propriétés algébriques des groupes d'homéomorphismes et de difféomorphismes de variétés. On appelle fragmentation la possibilité d'écrire un homéomorphisme en tant que composé d'homéomorphismes supportés dans des boules. Tout d'abord, nous étudions la longueur des commutateurs sur le groupe des homéomorphismes du tore et de l'anneau, ainsi que la norme de fragmentation, qui associe à tout homéomorphisme le nombre minimal de facteurs nécessaires pour écrire cet homéomorphisme en tant que composé d'homéomorphismes supportés dans des boules. Dans une deuxième partie de la thèse, nous abordons una autre propriété algébrique des groupes d'homéomorphismes et de difféomorphismes : la distorsion. Celle-ci est reliée de manière surprenante à des propriétés de fragmentation des homéomorphismes. / In this thesis, we are interested in various algebraic properties of groups of homeomorphisms and diffeomorphisms of manifolds. We call fragmentation the possibility to write a homeomorphism as a composition of homeomorphisms supported in balls. First, we study the commutator length on the group of homeomorphisms of the torus and of the annulus, as well as the fragmentation norm, which associates to any homeomorphism the minimal number of factors necessary to write this homeomorphism as a composition of homeomorphisms supported in balls. In a second part of this thesis, we deal with another algebraic property of homeomorphism and diffeomorphism groups: the distortion. This last notion is surprisingly related to fragmentation properties of homeomorphisms.

Every knapsack problem may be relaxed to a cyclic group problem. In 1969, Gomory found the subadditive characterization of facets of the master cyclic group problem. We simplify the subadditive relations by the substitution of complementarities and discover a minimal representation of the subadditive polytope for the master cyclic group problem. By using the minimal representation, we characterize the vertices of cardinality length 3 and implement the shooting experiment from the natural interior point. The shooting from the natural interior point is a shooting from the inside of the plus level set of the subadditive polytope. It induces the shooting for the knapsack problem. From the shooting experiment for the knapsack problem we conclude that the most hit facet is the knapsack mixed integer cut which is the 2-fold lifting of a mixed integer cut. We develop a cutting plane algorithm augmenting cutting planes generated by shooting, and implement it on Wong-Coppersmith digraphs observing that only small number of cutting planes are enough to produce the optimal solution. We discuss a relaxation of shooting as a clue to quick shooting. A max flow model on covering space is shown to be equivalent to the dual of shooting linear programming problem.

Le groupe de Cremona en n variables Cr_n(C) est le groupe des transformations birationnelles de l'espace projectif complexe de dimension n. Dans cette thèse, on étudie les groupes de Cremona en considérant certaines classes de „grands'' sous-groupes. Dans la première partie on considère des plongements algébriques de Cr_2(C) vers Cr_n(C). On décrit notamment quelques propriétés géométriques d'un plongement de Cr_2(C) dans Cr_5(C) dû à Gizatullin. En outre, on classifie tous les plongements algébriques de Cr_2(C) dans Cr_3(C) et on généralise ce résultat partiellement pour les plongements de Cr_n(C) dans Cr_{n+1}(C). Dans la deuxième partie, on regarde les suites des degrés des transformations birationnelles des variétés définies sur un corps quelconque. On montre qu'il n'existe qu'un nombre dénombrable de telles suites et on donne de nouvelles contraintes sur la croissance des degrés des automorphismes de l'espace affine de dimension n. Dans la troisième partie, on classifie les sous-groupes de Cr_2(C) qui ne contiennent que des éléments elliptiques, c'est-`a-dire des éléments dont les degrés des itérés sont bornés. On en déduit notamment l'alternative de Tits pour les sous-groupes quelconques de Cr_2(C). Dans la dernière partie on montre que tous les sous-groupes simples de type fini de Cr_2(C) sont finis et, sous l'hypothèse d'un lemme conjectural, qu'un groupe simple se plonge dans Cr_2(C) si et seulement s'il se plonge dans PGL_3(C). / The Cremona group in n-variables Cr_n(C) is the group of birational transformations of the complex projective n-space. This thesis contributes to the research on Cremona groups through the study of certain classes of „large'' subgroups. In the first part we consider algebraic embeddings of Cr_2(C) into Cr_n(C). In particular, we describe geometrical properties of an embedding of Cr_2(C) into Cr_5(C) that was discovered by Gizatullin. We also classify all algebraic embeddings from Cr_2(C) into Cr_3(C), and we partially generalize this result to embeddings of Cr_n(C) into Cr_{n+1}(C). In a second part, we look at degree sequences of birational transformations of varieties over arbitrary fields. We show that there exist only countably many such sequences and we give new obstructions on the degree growth of automorphisms of affine n-space. In the third part, we classify subgroups of Cr_2(C) containing only elliptic elements, i.e. elements whose iterates are of bounded degree. From this we deduce in particular the Tits alternative for arbitrary subgroups of Cr_2(C). In the last part, we show that every finitely generated simple subgroup of Cr_2(C) is finite and, under the hypothesis of an unproven conjectural lemma, that a simple group can be embedded into Cr_2(C) if and only if it can be embedded into PGL_3(C).

É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. / Given a complex of groups, when is it possible to deduce a property for its fundamental group out of the analogous properties of its local groups? This natural problem of geometric group theory has been adressed mainly for graphs of groups and complexes of finite groups. In this thesis, we develop geometric tools to study non-positively curved complexes of groups. We focus on properties of an asymptotic nature: EZ-structures, hyperbolicity. This allows us to prove a combination theorem for hyperbolic groups, which generalises a theorem of Bestvina-Feighn to complexes of groups of arbitrary dimension.

Un groupe de Baumslag-Solitar est un groupe dont la présentation est, pour p et q entiers non nuls. A chaque groupe de Baumslag-Solitar est associé un espace de déformation D p, q d'actions sur des arbres analogue à l'outre espace. Aut(BS(p, q)) agit sur cet espace ce qui induit une action du groupe des automorphismes extérieurs Out(BS(p,q)). Nous nous intéresserons au cas plus complexe où q est un multiple de p et dans un premier temps, nous démontrerons que tout automorphisme de BS(p, pn) est réductible ce qui signifie qu'il existe un BS(p,pn)-arbre T et une application laissant invariante un certain type de forêt. Ce résultat nous amènera à introduire un nouvel espace de déformation et une classification des automorphismes de BS(p, pn) en trois catégories : elliptique, parabolique ou hyperbolique. A l'aide de cette classification, nous démontrerons que tout automorphisme est à croissance soit polynomiale soit exponentielle. / A Baumslag-Solitar group is a group given by the group presentation, for p and q non-zero integers. For each Baumslag-Solitar group we consider a deformation space D p, q which is analogue of Culler-Vogtmann's Outer Space. The action of Aut(BS(p, q)) on D p, q induces an action of the outer automorphism group Out(BS(pq)). We will focus on the case where p divides q. Firstly, we will show that every automorphism of BS(p,pn) is reducible which means that we can find a BS(p,pn)-tree T and a map that leaves a certain type of subforest invariant. This result leads us to introduce a new deformation space and a classification of the automorphisms of BS(p,pn) in three types : elliptic, parabolic or hyperbolic. Using this classification, we will show that the growth of every automorphism of BS(p,pn) is exponential or polynomial.

Soit G un groupe dénombrable, qui se scinde en un produit libre de la forme G=G_1*...*G_k*F, où F est un groupe libre de type fini, et les G_i sont librement indécomposables et non isomorphes à Z. Nous montrons que le groupe Out(G) des automorphismes extérieurs de G satisfait l'alternative de Tits, dès lors que chacun des groupes G_i et Out(G_i) la satisfait. Par des méthodes similaires, nous montrons aussi l'alternative suivante pour tout sous-groupe H de Out(F_N), due à Handel et Mosher lorsque H est de type fini : soit H fixe virtuellement la classe de conjugaison d'un facteur libre propre de F_N, soit H contient un automorphisme complètement irréductible. Nos méthodes, géométriques, utilisent l'étude de la dynamique de l'action de certains sous-groupes de Out(G) sur des espaces hyperboliques. Nous décrivons notamment l'adhérence de l'outre-espace de G relatif aux G_i, et le bord de Gromov du complexe (hyperbolique) des scindements cycliques relatifs associé. Nous étudions par ailleurs les marches aléatoires sur Out(F_N). Sous un certain nombre de conditions sur la mesure de probabilité mu, nous montrons que presque toute trajectoire de la marche aléatoire sur (Out(F_N),mu) converge vers un point du bord de Gromov du complexe des facteurs libres de F_N, que nous identifions au bord de Poisson de (Out(F_N),mu). Par ailleurs, nous décrivons l'horofrontière de l'outre-espace. Ceci a des applications à l'étude de la croissance des classes de conjugaison de F_N sous l'effet de produits aléatoires d'automorphismes extérieurs. / Let G be a countable group that splits as a free product of the form G=G_1*...*G_k*F, where F is a finitely generated free group, and the groups G_i are freely indecomposable and not isomorphic to Z. We show that Out(G) satisfies the Tits alternative, as soon as all the groups G_i and Out(G_i) do. Similar techniques also yield another alternative for subgroups H of Out(F_N), due to Handel and Mosher when H is finitely generated, namely: either H virtually fixes the conjugacy class of some proper free factor of F_N, or H contains a fully irreducible automorphism. Our methods are geometric, and require understanding the dynamics of the action of some subgroups of Out(G) on Gromov hyperbolic spaces. In particular, we determine the closure of the outer space of G relative to the G_i's, as well as the Gromov boundary of the (hyperbolic) complex of relative cyclic splittings of G. We also study random walks on Out(F_N). Given a probability measure mu on Out(F_N) (satisfying some conditions), we prove that almost every sample path of the random walk on (Out(F_N),mu) converges to a point of the Gromov boundary of the free factor complex of F_N, which we identify with the Poisson boundary of (Out(F_N),mu). We also describe the horoboundary of outer space, and give applications to growth of conjugacy classes of F_N under random products of outer automorphisms.

La classe des graphes de groupes libres à groupes d'arêtes cycliques constitue une source importante d'exemples en théorie géométrique des groupes, en particulier dans le cadre des groupes hyperboliques. Un résultat récent de Wilton montre qu'un tel groupe à un bout et hyperbolique contient un sous-groupe de surface, répondant à une question attribuée à Gromov. Cette thèse est consacrée à l'étude de ces groupes lorsqu'ils se présentent comme des groupes fondamentaux de certains complexes carrés à courbure négative ou nulle. Les complexes carrés en question, appelés graphes tubulaires de graphes, sont obtenus en attachant des tubes (un tube est un produit cartésien d'un cercle avec l'intervalle unitaire) à une collection finie de graphes finis. Le but principal de cette thèse est de construire deux décompositions de base pour les groupes fondamentaux de graphes tubulaires de graphes : leur décomposition de Grushko et leur décomposition JSJ. Dans la première partie de la thèse, nous développons un algorithme en temps polynomial, dont l'entrée est un graphe tubulaire de graphes, et qui produit le scindement de Grushko de son groupe fondamental. Comme application, nous obtenons une version alternative d'un algorithme de Stallings, qui prend un ensemble fini de mots W dans un groupe libre F de rang fini, et décide s'il existe ou non un scindement libre de F relatif à W. Dans la deuxième partie de la thèse, nous développons un algorithme en temps doublement exponentiel, dont l'entrée est un graphe tubulaire de graphes avec un groupe fondamental hyperbolique à un bout, et qui produit le scindement JSJ du groupe fondamental. Nous remarquons qu'il s'agit du premier algorithme sur les scindements JSJ de groupes avec une borne effective sur la complexité de temps. La principale raison de l'efficacité de cet algorithme est que certaines propriétés asymptotiques du groupe, qui déterminent si le groupe se scinde au dessus un sous-groupe cyclique, admettent des caractérisations locales en raison de la structure cubique CAT(0). Comme application de ce résultat, nous obtenons un algorithme en temps doublement exponentiel, dont l'entrée est un groupe libre F de rang fini muni d'un ensemble fini de sous-groupes cycliques W tels que F est librement indécomposable relatif à W, et qui produit le scindement JSJ de F relativement à W. Une conséquence des résultats ci-dessus est que le problème d'isomorphisme pour les groupes considérés se réduit à l'algorithme de Whitehead. / The class of graphs of free groups with cyclic edge groups constitutes an important source of examples in geometric group theory, particularly of hyperbolic groups. A recent result of Wilton shows that any such group which is one-ended and hyperbolic contains a surface subgroup, answering a question attributed to Gromov. This thesis is devoted to the study of these groups when they arise as fundamental groups of certain nonpositively curved square complexes. The square complexes in question, called tubular graphs of graphs, are obtained by attaching tubes (a tube is a Cartesian product of a circle with the unit interval) to a finite collection of finite graphs. The main goal of this thesis is to construct two fundamental decompositions, the Grushko decomposition and the JSJ decomposition, of the fundamental groups of tubular graphs of graphs. In the first part of the thesis we develop an algorithm of polynomial time-complexity that takes a tubular graph of graphs as input and returns the Grushko decomposition of its fundamental group. As an application, we obtain an alternative version of an algorithm of Stallings, which takes a finite set of words W in a finite rank free group F as input, and decides whether or not there exists a free splitting of F relative to W. In the second part of the thesis we develop an algorithm of double exponential time-complexity that takes a tubular graph of graphs with one-ended hyperbolic fundamental group as input and returns the JSJ decomposition of the fundamental group. We remark that this is the first algorithm on JSJ decompositions of groups with an effective bound on the time-complexity. The main reason for the efficiency of this algorithm is that certain asymptotic properties of the group, which determine whether the group splits over a cyclic subgroup, admit local characterisations due to the CAT(0) cubical structure of these groups. As an application of this result, we obtain an algorithm of double exponential time-complexity that takes a finite rank free group F and a finite set of maximal cyclic subgroups W such that F is freely indecomposable relative to W as input and returns the relative JSJ decomposition of F relative to W. A consequence of the above results is that the isomorphism problem for the groups under consideration is reduced to the Whitehead algorithm.