Schedule & Abstracts

I will survey the results and discuss the ongoing program which aims to show that the problem of satisfiability of a system of equations in a free group (hyperbolic or even toral relatively hyperbolic group) is NP-complete.

Click here to see slides.

The subgroup membership problem for a group G asks whether a given group element g from G belongs to a given finitely generated subgroup H of G. Here, we are mainly interested in the case that G is infinite, where the representation of elements of G becomes relevant. In the case that G is finitely generated, one can represent elements of G by finite words over a generating set. But this representation is often not the most natural one.

Consider for instance the group GL(2,Z) of 2-dimensional integer matrices with determinant 1 or -1 (it is a finitely generated group). The most natural representation of an element of GL(2,Z) is certainly a matrix with binary encoded integers. Concerning the subgroup membership problem, it is straightforward to show that it can be solved in polynomial time for GL(2,Z) if elements of GL(2,Z) are represented by finite words over a finite set of generators (the proof uses the fact that GL(2,Z) is virtually-free.

On the other hand, if elements of GL(2,Z) are represented by matrices with binary encoded integers, the subgroup membership problem becomes more difficult. Nevertheless, we show that it can be solved in polynomial time. For the proof we extend Stallings folding procedure for free groups to graphs where edges are labelled with so called power words (finite words where binary encoded exponents are allowed).

Click here to see slides.

Joint results with F. Bassino and C. Nicaud.

Define the size of a subgroup H of PSL2(Z) to be the number of vertices of the Stallings graph of H. This is a finite number if H is finitely generated, and coincides with the index of H if H has finite index. Define also the isomorphism type of H (finitely generated) as the triple (l2, l3, r) of positive integers such that H is isomorphic to the free product of l2 copies of the cyclic group of order 2, l3 copies of the cyclic group of order 3 and a free group or order r (every subgroup of PSL2(Z) is of this form by Kurosh's theorem, since PSL2(Z) is isomorphic to the free product of the cyclic groups of order 2 and 3).

We compute the number of size n subgroups of PSL2(Z) and an asymptotic equivalent for this number. We also find the expected isomorphism type of a size n subgroup (namely (n^{1/2} + o(n^{1/2}), n^{1/3} + o(n^{1/3}), n/6 - 1/3 n^{2/3} + o(n^{2/3}))), and we prove a strong concentration result of the isomorphism type around this expected value. In particular, the (polynomial time) random generation algorithm that is naturally deduced from our enumeration method produces, with high probability, subgroups with isomorphism type 'near' (n^{1/2}, n^{1/3}, n/6 - 1/3 n^{2/3}).

These results can be specialized to count or randomly generated finite index subgroups (here, counting and asymptotic results were already known) or free subgroups of PSL2(Z).

We also describe a different enumeration method which allows us to count and randomly generated subgroups of a given size and isomorphism type. This leads to a proof that, generically, a size n subgroup of PSL2(Z) is not almost malnormal.

Click here to see slides.

The motivation for this talk is Gromov’s famous surface subgroup question: Does every one-ended hyperbolic group contain a subgroup which is isomorphic to the fundamental group of a closed surface of genus at least 2? Many classes of groups have been shown to contain surface subgroups, but for some the answer is still unknown.

I will present a family of 23 torsion free hyperbolic groups that act simply transitively on the vertices of hyperbolic triangular buildings of the smallest non-trivial thickness, and discuss the search for surface subgroups in these groups. The idea is to find periodic apartments using the combinatorics of the underlying geometry. The found periodic apartments then give rise to surface subgroups.

The search for periodic apartments giving genus 2 surface subgroups can be done with relatively simple algorithms, but for genera 3 and 4 expertise from computer scientists Savela, Oikarinen and Järvisalo was needed. They were able to perform exhaustive search for genus 3 using novel SAT encodings and a specialised orderly algorithm, and also for genus 4 with the aid of massive parallel computing. As a result seven groups have been shown to have surface subgroups, leaving 14 of the 23 groups for further inspection.

Based on joint work with Alina Vdovina, Jarkko Savela, Emilia Oikarinen, and Matti Järvisalo.

Click here to see slides.

The class of Artin groups we consider is the class of those Artin groups for which no edge of the defining graph is labelled by 3.

We show that for this class f(n)=n^6 is an isoperimetric function. In particular, groups in this class have solvable word problem.

We use small cancellation theory for relative presentations.

Click here to see slides.

Topological full groups of minimal subshifts are an important source of exotic examples in geometric group theory, as well as being powerful invariants of symbolic dynamical systems. In 2011, Grigorchuk and Medynets proved that TFGs are LEF, that is, every finite subset of the multiplication table occurs in the multiplication table of some finite group. In this talk we explore how the growth of the finite groups which occur reflects asymptotic properties of the associated subshift. Joint work with Daniele Dona.

Click here to see slides.

Joint work with Marston Conder, Alex Lubotzky and Francois Thilmany

Given a string Coxeter system (W,S), we construct highly regular quotients of the 1-skeleton of its universal polytope P, which form an infinite family of expander graphs when (W,S) is indefinite and P has finite vertex links. The regularity of the graphs in this family

depends on the Coxeter diagram of (W,S). The expansion stems from superapproximation applied to (W,S). This construction is also extended to cover Wythoffian polytopes. As a direct application, we obtain several notable families of expander graphs with high levels of regularity, answering in particular a question posed by Chapman, Linial and Peled positively.

Given a small pattern H and a large network, how often is H contained in the network? This problem is fundamental in computational complexity theory and occurs in a diverse set of disciplines such as statistical physics, database theory, bioinformatics and network science, only to name a few. Unfortunately, under standard assumptions from complexity theory related to the famous P vs NP problem, there are families of patterns for which efficient algorithms are impossible, and a recent line of research has focussed on the quest to precisely identify these “hard patterns”.

While significant progress has been made, this quest is still far from being completed. However, deep connections to commutative combinatorial algebra have been discovered, which allows to rephrase the question in purely combinatorial terms, for instance, via properties of certain simplicial complexes and Cayley graphs.

In this talk, I will give an overview of the state of the art including recent advances to tackle the problem via (explicit) constructions of low-degree Cayley Graph Expanders. Additionally, I will present the most pressing open problems. No prior knowledge of complexity theory will be required.

Based on joint work with Julian Dörfler, Norbert Peyerimhoff, Johannes Schmitt, Jakob Stix, Alina Vdovina, and Philip Wellnitz.

Click here to see slides.

Finite graphs with strong expansion properties have found applications in numerous areas of Theoretical Computer Science. In this talk I will focus on just one of these areas, proof complexity, and present several examples illustrating the corresponding applications. They pertain to a remarkably wide array of models and proof systems actively studied these days.

The talk will be self-contained, no prior knowledge of proof complexity will be assumed.

Click here to see slides.

A finite graph that can be obtained from a given graph by contracting edges and removing vertices and edges is called a minor of this graph. Minors have played an important role in graph theory, ever since the well-known result of Kuratowski that characterised planar graphs as those that do not admit the complete graph on 5 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.

Click here to see slides.

A self-similar group acts on an infinite, d-ary, rooted tree by automorphisms and induces a covering sequence of finite Schreier graphs X_n, one for each level of the tree (X_{n+1} covers X_n in d-to-1 fashion). Calculation of the spectra of these graphs (and their limits) is aided by the self-similarity of the group action and such calculations have been successfully performed in some situations (Grigorchuk, Zuk, Bartholdi,...).

In this talk, we will recall the necessary definitions, along with a few well known examples, and then present a treatment of the class of examples coming from conservative polynomials, introduced by Smale in his work on the Fundamental Theorem of Algebra. In particular, for every r>1, we will provide examples of groups whose Schreier spectrum is described by backward orbits of polynomials of degree r (the new eigenvalues at level n+1 are the inverse images of the eigenvalues on level n under a Chebyshev-like polynomial map of degree r).

Click here to see slides.

TBC

“What can one describe by first-order formulas in a given structure A?” - is an old and interesting question. Of course, this depends on the structure A. For example, in a free group only cyclic subgroups (and the group itself) are definable in the first-order logic, but in a free monoid of finite rank any finitely generated submonoid is definable. A structure A is called rich if the first-order logic in A is equivalent to the weak second order logic. Surprisingly, there are a lot of interesting groups, rings, semigroups, etc., which are rich. I will talk about some of them and then describe various algebraic, geometric, and algorithmic properties that are first-order definable in rich structures. Weak second order logic can be introduced into algebraic structures in different ways: via HF-logic, or list superstructures over A, or computably enumerable infinite disjunctions and conjunctions, or via finite binary predicates, etc. I will describe a particular form of this logic which is especially convenient to use in algebra and show how to effectively translate such weak second order formulas into the equivalent first-order ones in the case of a rich structure A.