Computations in Groups and Applications

Garside groups have been first introduced by P.Dehornoy and L.Paris in 1990. In many aspects, Garside groups extend braid groups and more generally finite-type Artin groups. These are torsion-free groups with a word and conjugacy problems solvable, and they are groups of fractions of monoids with a structure of lattice with respect to left and right divisibilities. It is natural to ask if there are additional properties Garside groups share in common with the intensively investigated braid groups and finite-type Artin groups. In this talk, I will introduce the Garside groups in general, and a particular class of Garside groups, that arise from certain solutions of the Quantum Yang-Baxter equation. I will describe the connection between these theories arising from different domains of research, present some of the questions raised for the Garside groups and give some partial answers to these questions.

Many infinite groups satisfy orderability type properties that force quite interesting combinatorial properties that have attracted the attention of some people over the last years. For instance, free groups cannot be exhibited as groups of fractions of finitely-generated monoids. In this talk I will give an overview on this type of phenomena and present some open questions and ideas for future research.

We describe solutions to the problem of elementary classification in the class of group algebras of free groups. We will show that unlike free groups, two group algebras of free groups over infinite fields are elementarily equivalent if and only if the groups are isomorphic and the fields are equivalent in the weak second order logic. We will show that the set of all free bases of a free group $F$ is 0-definable in the group algebra $K(F)$ when $K$ is an infinite field, the set of geodesics is definable, and many geometric properties of $F$ are definable in $K(F)$. Therefore $K(F)$ ``knows" some very important information about $F$. We will show that similar results hold for group algebras of limit groups. These are joint results with A. Myasnikov.

Following ideas that go back to Cannon, we show the rationality of various growth functions counting embeddings of convex subgraphs in locally-finite graphs with the (relative) falsification by fellow traveller property. One of our applications concerns Scheier coset graphs of hyperbolic groups relative to quasi-convex subgroups, we show that these graphs have rational growth, the falsification by fellow traveller property, and the existence of a lower bound for the growth rate independent of the generating set and the quasi-convex subgroup (provided it that has infinite index).

Garside shadows in a Coxeter system (W,S) appear in relation to the question of solving the conjugacy problem in the context of a general Artin-Tits Braid group. In this talk we will discuss properties and open problems about a family of finite state automata that recognize the language of finite reduced words for (W,S) and built out of finite Garside shadows. (based on a joint work with Philippe Nadeau and Nathan Williams)

Geodesics play an essential role in studying Cayley graphs of groups. I will define the notion of a uniquely labelled geodesic and study such geodesics in Cayley graphs of certain Coxeter groups. I will give a formula for the maximal length of such a geodesic. More specifically, I will present a generating function which describes the number of uniquely labelled geodesics with each label, from which we can deduce results about the overall number of such geodesics. This is joint work with Kirill Zainoulline.

We will discuss a homological version of homotopical results of Bridson, Howie, Short, Miller, Kuchkuck on fibre products of groups. In particular we will show that in some cases the homological version of the n-(n+1)-(n+2) Conjecture holds. This is joint work with Francismar Lima.

We will survey some of the known relationship between group orderings (linear or circular) and its associated dynamics on one dimensional manifold (the line or the circle).

Non-commutative cryptography seeks to develop cryptosystems that utilize algorithmic problems from group theory for their hardness assumptions. The security of such systems is contingent upon the computational complexity of the chosen algorithmic problem in the underlying platform group. In this talk, we analyze the computational complexity of the conjugacy search problem in a certain family of metabelian groups. We prove that in general the time complexity of the conjugacy search problem for these groups is at most exponential. For a subfamily of groups we prove that the conjugacy search problem is polynomial. We also show that for some of these groups the conjugacy search problem reduces to the discrete logarithm problem. This is a joint work with Delaram Kahrobaei and Conchita Martinez-Perez.

Let $G$ be a finitely generated solvable subgroup of $GL_n(C)$ with a connected Zariski closure, and let $\mu$ be a probability measure on $G$ whose support generates $G$ as a semigroup. By a theorem of Rosenblatt, if $G$ is not virtually nilpotent then it contains a non-abelian free semigroup. We will prove a probabilistic generalization of this result, namely, that under some necessary assumptions on the underlying measure $\mu$, if $(X_n)_{n \ge 1}$ and $(Y_n)_{n \ge 1}$ are independent $\mu$-random walks on $G$, then the pair $(X_n, Y_n)$ generates a non-abelian free semigroup with probability approaching $1$ as $n \to \infty$.

In this talk, we will discuss an algorithm that solves the word problem in relatively hyperbolic groups, and its complexity whenever the solution to the word problem in parabolic subgroups is given.

A subgroup $H$ of a group $G$ is called conjugacy stable if every pair of elements from $H$ that are conjugate in $G$, are also conjugate in $H$. In this talk we show how conjugacy stability of f.g. subgroups can be effectively checked in certain classes of groups. This is joint work with Isabel Fernandez Martinez.