Tag - Free groups

Enric Ventura: The central tree property and some average case complexity results for algorithmic problems in free groups

8th December, 2023

We study the average case complexity of the Uniform Membership Problem for subgroups of free groups, and we show that it is orders of magnitude lower than the worst case complexity of the best known algorithms. This applies both to subgroups given by a fixed number of generators, and to subgroups given by an exponential number of generators. The main idea behind this result is to exploit a generic property of tuples of words, called the central tree property. Another application is given to the average case complexity of the relative primitivity problem, using Shpilrain's recent algorithm to decide primitivity in a free group, whose average case complexity is a constant depending only on the rank of the ambient free group.

Ilya Kapovich: Primitivity index bounds in free groups, and the second Chebyshev function

13th October, 2023

Motivated by results about 'untangling' closed curves on hyperbolic surfaces, Gupta and Kapovich introduced the primitivity and simplicity index functions for finitely generated free groups, dprim(g;FN) and dsimp(g;FN), where 1 ≠ g ∈ FN, and obtained some upper and lower bounds for these functions. In this talk, we study the behaviour of the sequence dprim(anbn; F(a,b)) as n → ∞. Answering a question of Kapovich, we prove that this sequence is unbounded and that for ni=lcm(1,2,...,i), we have |dprim(anibni; F(a,b))-log(ni)| = o(log(ni)). By contrast, we show that for all n ≥ 2, one has dsimp(anbn;F(a,b)) = 2.

In addition to topological and group-theoretic arguments, number-theoretic considerations, particularly the use of asymptotic properties of the second Chebyshev function, turn out to play a key role in the proofs.

Olga Kharlampovich: Fraïssé limits of limit groups

29th October, 2020

We modify the notion of a Fraïssé class and show that various interesting classes of groups, notably the class of non-abelian limit groups and the class of finitely generated elementary free groups, admit Fraïssé limits. We will also discuss countable elementary free groups.

Ana Khukhro: A new characterization of virtually free groups

4th September, 2020

A finite graph that can be obtained from a given graph by contracting edges and removing vertices and edges is said to be a minor of this graph. Minors have played an important role in graph theory, ever since the well-known result of Kuratowski that characterized planar graphs as those that do not admit the complete graph on five vertices nor the complete bipartite graph on (3,3) vertices as minors. In this talk, we will explore how this concept interacts with some notions from geometric group theory, and describe a new characterisation of virtually free groups in terms of minors of their Cayley graphs.

Murray Elder: Rewriting systems and geodetic graphs

4th September, 2020

I will describe a new proof, joint with Adam Piggott (UQ), that groups presented by finite convergent length-reducing rewriting systems where each rule has left-hand side of length 3 are exactly the plain groups (free products of finite and infinite cyclic groups). Our proof relies on a new result about properties of embedded circuits in geodetic graphs, which may be of independent interest in graph theory.