# Computations in Groups and Applications

Organizers:

- Inna Bumagin (Carleton University)
- Delaram Kahrobaei (CUNY)

Schedule:

- Thursday, Jul 27 [McGill U., Bronfman Building, Room 45]
- 11:45 Fabienne Chouraqui (University of Haifa, Israel), THE GARSIDE GROUPS AND SOME OF THEIR PROPERTIES
- 12:15 Andrés Navas Flores (Universidad de Santiago de Chile, Chile), Some combinatorial problems associated to orderability properties of groups
- 14:15 Olga Kharlampovich (Hunter College, USA), What does a group algebra of a free group ``know'' about the group?
- 14:45 Yago Antolin Pichel (Madrid, Spain), Counting with the falsification by fellow traveller property
- 15:45 Christophe Hohlweg (University of Quebec, Montreal, Canada), Garside Shadows and Automata in Coxeter groups
- 16:15 Elisabeth Fink (University of Ottawa, Canada), Labelled geodesics in Coxeter groups
- Friday, Jul 28 [McGill U., Bronfman Building, Room 45]
- 11:45 Dessislave Kochloukova (UNICAMP, Campinhas, Brasil), Fibre products of groups
- 12:15 Cristobal Rivas (Universidad de Santiago de Chile), Dynamical properties of invariant orderings on groups
- 14:15 Jonathan Gryak (CUNY Graduate Center, USA), On the Conjugacy Problem in Certain Metabelian Groups
- 14:45 Keivan Mallahi-Karai (Jacob University, Germany), Random semigroups in solvable linear groups
- 15:45 Ming Ming Zhang (Carlton University, Canada), Time complexity of the word problem in relatively hyperbolic groups
- 17:00 Denis Serbin (Stevens Institute of Technology, USA), Detecting conjugacy stability of subgroups

- Fabienne Chouraqui

University of Haifa, IsraelTHE GARSIDE GROUPS AND SOME OF THEIR PROPERTIESGarside 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. - Andrés Navas Flores

Universidad de Santiago de Chile, ChileSome combinatorial problems associated to orderability properties of groupsMany 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. - Olga Kharlampovich

Hunter College, USAWhat does a group algebra of a free group ``know'' about the group?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. - Yago Antolin Pichel

Madrid, SpainCounting with the falsification by fellow traveller propertyFollowing 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). - Christophe Hohlweg

University of Quebec, Montreal, CanadaGarside Shadows and Automata in Coxeter groupsGarside 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) - Elisabeth Fink

University of Ottawa, CanadaLabelled geodesics in Coxeter groupsGeodesics 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. - Dessislave Kochloukova

UNICAMP, Campinhas, BrasilFibre products of groupsWe 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. - Jonathan Gryak

CUNY Graduate Center, USAOn the Conjugacy Problem in Certain Metabelian GroupsNon-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. - Keivan Mallahi-Karai

Jacob University, GermanyRandom semigroups in solvable linear groupsLet $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$. - Ming Ming Zhang

Carlton University, CanadaTime complexity of the word problem in relatively hyperbolic groupsIn 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. - Denis Serbin

Stevens Institute of Technology, USADetecting conjugacy stability of subgroupsA 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.