Swiss Doctoral Program in Mathematics

Spring School at Les Diablerets

Geometry, Topology and Computation in Groups

100 Years since Dehn's Decision Problems

7 - 12 March 2010

Hotel les Sources, Les Diablerets, Switzerland

 

New! Notes and references related to the talks.

Martin Bridson's Links

The geometry of the word problem
Non-positive curvature and complexity for finitely presented groups
The quadratic isoperimetric inequality for mapping tori of free group automorphisms
There is only one gap in the isoperimetric spectrum
Snowflake groups, Perron-Frobenius eigenvalues, and isoperimetric spectra

Pierre de la Harpe's Notes

Bettina Eick's Slides

Sarah Rees' Slides

Olga Kharlampovich's Slides (I)

Olga Kharlampovich's Slides (II)

Conference Photos

Organizers

Laura Ciobanu, University of Fribourg (laura.ciobanu@unifr.ch);
Tatiana Smirnova-Nagnibeda, University of Geneva (Tatiana.Smirnova-Nagnibeda@unige.ch);

Opening Lecture

Pierre de la Harpe (Geneva)

Invited Speakers

Rostislav Grigorchuk (Texas A&M) Alexei Miasnikov (McGill U.) Martin Bridson (Oxford)
Sarah Rees (Newcastle U.) Ilya Kapovich (UIUC) Francois Dahmani (U. Toulouse)
Laurent Bartholdi (Göttingen)                    Bettina Eick (TU Braunschweig)              Olga Kharlampovich (McGill U.)
Denis Osin (Vanderbilt) Volker Diekert (Stuttgart) Patrick Dehornoy (Caen)

Titles and Abstracts

Schedule of Talks

Preparatory lectures will take place in Fribourg on February 24.

Schedule

The arrival day is Sunday, March 7. Dinner will be served in the Hotel les Sources at about 7 p.m.
The scientific program begins on Monday, March 8, at 9 a.m.
The conference ends at lunchtime on Friday, March 12.

There will be four lectures per day: three morning lectures from 9 a.m. till noon, and one afternoon lecture at 6 p.m.
Coffee and tea will be served at 9.50 a.m. in the conference center and at 5 p.m. in the Hotel les Sources.
Lunch time is 12.15 (with a possibility to order a picnic: orders have to be placed before 9 a.m. the same day). Dinner time is 7 p.m.

Your stay

Rooms have been booked for all participants at Hôtel les Sources and Hotel le Chamois.
The talks take place in the conference center 5 minutes walk from the hotels.

The price of accommodation and full board at the Hôtel Les Sources (to be paid at the conference site)
for participants from EPFL, Uni-Fribourg, Uni-Genève, Uni-Neuchâtel, Uni-Bern, Uni-Basel:
in a double room: CHF 75 for the whole period
in a single room: CHF 150 for the whole period
for other participants:
in a double room: CHF 128 per person per night
in a single room: CHF 149 per person per night

How to get there


How to get to Les Diablerets
Swiss Railroad
You can view a smal map of the hotel surroundings, including the railway station in Les Diablerets and the conference center, under "Situation" on the hotel Les Sources website.

Scientific Committee

Laura Ciobanu (Fribourg)
Tatiana Nagnibeda-Smirnova (Geneva)
Enric Ventura (Barcelona)
Armando Martino (Southampton)
Andrew Duncan (Newcastle)

Supported by

                       

Titles and Abstracts

Minicourses

Martin Bridson (Oxford): Groups with quadratic Dehn functions

I shall begin by sketching a proof of the basic equivalence between the problem of filling loops in the universal cover of a closed manifold and the word problem for the fundamental group of the manifold. I shall explain the geometry behind the Brady-Bridson snowflake construction, proving that Dehn functions are dense in the super-quadratic range. I'll then concentrate on the class of finitely presented groups that satisfy a quadratic isoperimetric inequality, surveying the groups that are known to lie in this class and discussing what properties they have in common. I plan in particular to discuss what is known for lattices in semisimple Lie groups and what is known about the homological finiteness of groups with a quadratic Dehn function. The third lecture will include an explanation of the main ideas that go into proving that all free-by-cyclic groups satisfy a quadratic isoperimetric inequality.

Alexei Miasnikov (McGill U.): tba

Denis Osin (Vanderbilt): Filling in groups acting on hyperbolic spaces

We will start with a brief discussion of equivalent definitions and basic properties of relatively hyperbolic groups. We will then discuss a generalization of relative hyperbolicity based on the notion of a hyperbolically embedded subgroup. Examples of such subgroups naturally occur when a group admits a 'nice' action on a hyperbolic space. Finally we will show how hyperbolically embedded subgroups can be used to generalize the Gromov-Thurston theory of Dehn filling in hyperbolic 3-manifolds. Some applications to hyperbolic and relatively hyperbolic groups, mapping class groups, and outer automorphism groups of free groups will be presented.

Sarah Rees (Newcastle): The Word Problem in the Chomsky Hierarchy

I shall talk about the word problem for groups, and how hard it is to solve it. I'll view the word problem of G=< X> as the recognition of the set WP(G,X) of words over X that represent the identity, and look to relate properties of G to the complexity of WP(G,X) as a formal language, that is to the complexity of the Turing machine (model of computation) needed to recognise that set.

Talks

Laurent Bartholdi (Göttingen): Automatically presented groups and algebras

Francois Dahmani (U. Toulouse): Hyperbolic geometry to solve instances of Dehn's third problem, the isomorphism problem

The problem of algorithmically deciding whether two finite presentations define isomorphic groups is unsolvable (Adian, Rabin). However, in 1995 Sela proposed a solution to the isomorphy problem for a class of torsion-free rigid hyperbolic groups. The geometry of negative curvature allows to provide strong structural features for groups, and also gives possibilities to effectively compute in these groups (e.g. the problem of solving equations in these groups is algorithmically solvable, in a certain sense). In joint works with Daniel Groves, and Vincent Guirardel, we completed and extended Sela's program to a wide class of relatively hyperbolic groups, and to all hyperbolic groups. This work required revisiting an important algorithm of Makanin for solving equations in free groups, in a geometric and dynamical perspective.

Patrick Dehornoy (Caen): Le probleme de mots pour les groupes de tresses

Volker Diekert (Stuttgart): On Computing Geodesics in Baumslag-Solitar Groups

The Baumslag-Solitar group BS(p,q) is a one-relator group defined by BS(p,q) :=< a,t | t a^p t^{-1}=a^q>. In my lecture I will give a dynamic programming method for computing geodesic words. As a consequence of our method we will see that if p divides q, then the set of horocyclic elements (elements in the cyclic subgroup < a >) in length-lexicographical normal form is a deterministic (and unambiguous) linear context-free (one-counter) language; and it can be recognized in log-space. The growth series of the horocyclic subgroup is therefore a rational function (quotient of two polynomials) and can be calculated effectively. Rationality of the growth series is due to Freden et al. who showed it with a different method. The growth tells us how many group elements are in balls are in balls of a certain radius around the origin of the Cayley graph of BS(p,q). If p divides q our main result is a square-time algorithm to compute the geodesic length of all group elements. This is a positive partial answer to a question raised by Elder et al. in 2009. In the case where p does not divide q it might be that the problem is actually Co-NP-complete. The investigation of the general case remains a challenging research project. My lecture is based on a joint work with Jurg Laun.

Bettina Eick (TU Braunschweig): The classification of p-groups by coclass

This is a survey on the recent advances on the classification of p-groups. It briefly discusses the classification of p-groups by their order. Then it introduces the idea of coclass and describes coclass graphs. Finally, it surveys some of the recent results on the classification by coclass.

Rostislav Grigorchuk (Texas A&M): Torsion images of Coxeter groups and the Wiegold problem

Ilya Kapovich (UIUC): Geometry of Out(F_n) and geodesic currents on free group

Olga Kharlampovich (McGill U.): Interesting examples of solvable groups

I am going to discuss algorithmic problems for solvable groups, describe my construction of a f.p. 3-step solvable group with undecidable word problem, discuss interesting properties of this group and other interesting examples of solvable groups.

Pierre de la Harpe (Geneva): A propos de Max Dehn, de topologie et de théorie des groupes