Combinatorics and Computation in Groups

November 22, 2017

The meeting Combinatorics and Computation in Groups will be held on Wednesday 22 November 2017 in the Seminar Room, Level 1 of the International Centre for Mathematical Sciences (ICMS), 15 South College Street, Edinburgh.



Please make your own arrangements for lunch. ICMS is close to the main campus of Edinburgh University.
There are plenty of restaurants, cafes and sandwich shops in the vicinity, for example in George IV Bridge, Potter Row and Nicholson Street.


1:30-2:30 Sarah Rees (Newcastle): Rewriting in Artin groups

I'll talk about the solution of the word problem in Artin groups, focusing on recent attempts to find an approach that might work for the whole spectrum of those groups. I'll refer to work by a number of authors, from Garside, Deligne, Brieskorn&Saito, via Appel&Schupp, to very recent work, by myself and Derek Holt, by Eddy Godelle and by Patrick Dehornoy.

2:45-3:45 Derek Holt (Warwick): Computing in infinite groups

We survey algorithms for computing in (generally infinite) groups defined by finite presentations, with an emphasis on the existence and availability of effective implementations.

The talk will focus mainly on the Generalised Word Problem and the Conjugacy Problem.

There are not many methods available for the Generalised Word Problem when the index of the subgroup H of G is infinite. The Stallings Folding method for subgroups of free groups can be generalised to quasiconvex subgroups of automatic groups provided that we can compute a so-called coset automatic structure. This is possible, for example, for quasiconvex subgroups of hyperbolic groups.

The Conjugacy Problem in certain types of groups (braid groups and polycyclic groups, for example) has received a lot of attention recently resulting from potential applications to cryptography. But in this talk we focus on the problem in hyperbolic groups, which can theoretically be solved in (almost) linear time, but for which effective implementations seem to be more difficult.

3:45-4:15 Tea/Coffee Break

4:15-5:15 Laura Ciobanu (Heriot-Watt): Solving equations in groups

Solving equations with coefficients that are elements of some group and the solutions take values in the same group can be seen as akin to solving diophantine equations in number theory, answering questions from linear algebra or more generally, algebraic geometry. The difficulty of the problem depends very much on the chosen group.

In this talk I give a survey on what is known about solving equation in infinite nonabelian groups, with emphasis on free groups. I will also make connections to algebraic geometry over groups, logic and formal languages.



There will be an early evening meal at 6:00 at Howies on Victoria Street, for all who are able to stay. Please let us know by Monday 20 November if you wish to come to the meal: email


Click here for a map and directions to ICMS. Waverley Station is towards the top of this map, adjacent to Waverley Bridge. It is about 10 minutes walk from the station to ICMS.

This meeting is supported by a New Appointment grant from the London Mathematical Society,

The local organiser for this meeting is Laura Ciobanu.