# North British Geometric Group Theory Seminar

## The next NBGGT will be in St Andrews, on Wednesday 22nd May, 2019.

All talks will be in Theatre C of the Mathematical Institute, which is Building 14 on this map.

If you catch the bus from Leuchars, there is a bus stop on the main road opposite the Gateway building. This is more convenient than continuing on to the bus station.

** Lunch ** Unfortunately there are no sit-in lunch options available near the maths department that reliably have spaces, so if you need lunch beforehand I suggest the Rector's Café, in the Students Union building on Market St (near the bus station). Alternatively, takeaway options are (hopefully) available in the Medical building (17 on the map) or the Physics building (15 on the map), and we will probably eat lunch at around 12.30 in the Staff room of the Mathematical Institute.

The schedule is as follows:

1.30pm **Ben Martin** (Aberdeen) *Growth in finitely generated nilpotent groups*

** Abstract: **
Various growth functions on finitely generated groups have been studied over the last several decades: for instance, the word growth function, which counts the number of group elements that can be written as a word of length at most * n* in a given set of generators. A celebrated result of Gromov is that a finitely generated group has polynomial word growth if and only if it is virtually nilpotent. I will discuss two other types of growth for finitely generated nilpotent groups, namely subgroup growth and representation growth. This involves ideas from logic and model theory, including the notion of a *p*-adic integral.

2.45pm **Derek Holt** (Warwick) *The compressed word problem in groups*

** Abstract: **
Let *G* be a finitely generated group. The word problem WP(*G*) of *G* is the
problem of deciding whether a given word *w* over the elements of some finite
generating set and (their inverses) of *G* represents the identity element of *G*.
It was proved in the 1950s that there are groups with unsolvable word problem,
but for groups with solvable word problem, it is interesting both in theory and
in practice to study the time and space complexity of WP(*G*) as a function of
the length of the input word *w*. Many of the groups that arise in geometric
group theory, including nilpotent groups, hyperbolic groups, Coxeter groups,
Artin groups, braid groups, and mapping class groups are known to have
word problem solvable in low degree polynomial time (usually linear or
quadratic).
For the compressed word problem CWP(*G*), words are input in compressed form as
straight line programs or, equivalently, as context-free grammars. For some
words, such as powers of generators, the uncompressed word can be exponentially
longer than its compressed version. So the complexity of CWP(*G*) could
conceivably be exponentially greater than WP(*G*). As motivation for studying
this question, we observe that it is easily shown that the ordinary word
problem in finitely generated subgroups of Aut(*G*) is polynomial time reducible
to CWP(*G*).

It turns out that for some classes of (finitely generated) groups, including
nilpotent groups, Coxeter groups, and right-angled Artin groups, CWP(*G*)
is solvable in polynomial time, whereas for others, such as the wreath product
of a nonabelian finite group by an infinite cyclic group, it has been proved
to be NP-hard.

In this talk, we will discuss a (fairly) recent result of Lohrey and Schleimer
that, for hyperbolic groups *G*, CWP(*G*) is solvable in polynomial time, and
speculate on whether this result can be extended to include groups
that are hyperbolic relative to a collection of abelian subgroups.

3.45pm **Tea and Coffee**

4.15pm **Gerald Williams** (Essex) *Generalized graph groups with balanced presentations*

** Abstract: ** A balanced presentation of a group is one
with an equal number of generators and relators.
Since presentations with more generators than relators define
infinite groups, balanced presentations
present a borderline situation where both finite and infinite groups
can be found. It is of interest to find which balanced presentations can define finite groups, and what groups can arise.
We consider groups defined by balanced presentations with the
property that each relator is of the form
R(x,y) where R is some fixed word in two generators. Examples of such groups include Right Angled Artin Groups,
Higman groups, and cyclically presented groups in which the relators involve exactly two generators. To
each such presentation we associate a directed graph whose vertices correspond to the generators and whose
arcs correspond to the relators. Extending work of Pride, we show that if the graph is triangle-free
then the corresponding group cannot be trivial or finite of rank greater than 2.
This is joint work with Johannes Cuno.

**Dinner**at a restaurant in town, near the bus station. Please email Colva Roney-Dougal by 12 noon on Friday 17th May if you'd like to come to dinner.

Please send any queries to Colva Roney-Dougal.