The conjugacy length function of a group Γ determines, for a given a pair of conjugate elements u,v ∈ Γ, an upper bound for the shortest γ in Γ such that uγ = γv, relative to the lengths of u and v. This thesis focuses on estimating the conjugacy length function in certain finitely generated groups. We first look at a collection of solvable groups. We see how the lamplighter groups have a linear conjugacy length function; we find a cubic upper bound for free solvable groups; for solvable Baumslag--Solitar groups it is linear, while for a larger family of abelian-by-cyclic groups we get either a linear or exponential upper bound; also we show that for certain polycyclic metabelian groups it is at most exponential. We also investigate how taking a wreath product effects conjugacy length, as well as other group extensions. The Magnus embedding is an important tool in the study of free solvable groups. It embeds a free solvable group into a wreath product of a free abelian group and a free solvable group of shorter derived length. Within this thesis we show that the Magnus embedding is a quasi-isometric embedding. This result is not only used for obtaining an upper bound on the conjugacy length function of free solvable groups, but also for giving a lower bound for their L_p compression exponents. Conjugacy length is also studied between certain types of elements in lattices of higher-rank semisimple real Lie groups. In particular we obtain linear upper bounds for the length of a conjugator from the ambient Lie group within certain families of real hyperbolic elements and unipotent elements. For the former we use the geometry of the associated symmetric space, while for the latter algebraic techniques are employed.

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)

Mikhail Gromov’s work on hyperbolic groups in the late 1980s contributed to the formation of geometric group theory as a distinct branch of mathematics. The creation of hyperbolic metric spaces showed it was possible to define a large class of hyperbolic groups entirely geometrically yet still be able to derive significant algebraic properties. The objectives of this thesis are to provide an introduction to geometric group theory through the lens of quasi-isometry and show how hyperbolic groups have solvable word problem. Also included is the Stability Theorem as an intermediary result for quasi-isometry invariance of hyperbolicity.

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.