Fall 2019

All the talks are 4:00pm-5:00pm in Room 5417 at the CUNY Graduate Center.

Wine and cheese are served afterwards in the math lounge on the 4th floor (Room 42414)

*September 13,  Heejoung Kim (University of Illinois at Urbana-Champaign)

TitleAlgorithms detecting stability and Morseness for finitely generated groups


For a word-hyperbolic group G, the notion of quasiconvexity is independent on the choice of a generating set and a quasiconvex subgroup of G is quasi-isometrically embedded in G. In 1994 Kapovich provided a partial algorithm which, on input a finite set S of G, halts if S generates a quasiconvex subgroup of G and runs forever otherwise.

However, beyond word-hyperbolic groups, the notion of quasiconveixty is not as useful.

For a finitely generated group, there are two recent generalizations of the notion of a quasiconvex subgroup of a word-hyperbolic group, a ``stable'' subgroup and a ``Morse'' subgroup.

In this talk, we will discuss various detection and decidability algorithms for stability and Morseness of a finitely generated subgroup of mapping class groups, right-angled Artin groups, toral relatively hyperbolic groups.

*September 20,  Susan Hermiller (University of Nebraska)

TitleAlgorithms for groups of PL homeomorphisms


The group PL_+(I) of orientation-preserving piecewise-linear homeomorphisms of the unit interval includes many important subgroups, most notably R. Thompson's group F. We study dynamical properties of the homeomorphisms in `computable' subgroups of PL_+(I) (including F) to give an algorithm which determines whether or not any given finite subset of such a computable group generates a solvable group. We give an application of this to solving the subgroup membership problem for a large family of finitely generated solvable subgroups of finitely generated groups of PL homeomorphisms. This is joint work with Collin Bleak and Tara Brough.

*September 27,   

*October 4,  Ariane Masuda and Johann Thiel (New York City College of Technology)

TitleSubgroups of SL2(Z)$ characterized by certain continued fraction representations

Abstract:  For positive integers u and v, let $L_u=\begin{bmatrix} 1 & 0 \\ u & 1 \end{bmatrix}$ and $R_v=\begin{bmatrix} 1 & v \\ 0 & 1 \end{bmatrix}$. Let Su,v be the monoid generated by Lu and Rv, and Gu,v be the group generated by Lu and Rv. In this talk we will show an extension of a characterization of matrices $M=\begin{bmatrix}a & b \\c & d\end{bmatrix}$ in Sk,k and Gk,k when k  2 given by Esbelin and Gutan to Su,v when u,v ≥ 2 and Gu,v when u,v  3. We will present a simple algorithmic way of determining if M is in Gu,v using a recursive function and the short continued fraction representation of b/d.

*October 18, Denis Osin (Vanderbilt  University)

Title: Quasi-isometric diversity of groups

Abstract: Quasi-isometry is an equivalence relation that identifies metric spaces having the same large scale geometry. It is especially useful in geometric group theory and plays essentially the same role as the isomorphism relation in algebra. It is well-known that the set of quasi-isometry classes of finitely generated groups has the cardinality of the continuum. Indeed, this immediately follows from the existence of continuously many groups with pairwise inequivalent growth functions proved by Grigorchuk in the 80s. A different proof, using small cancellation theory, was given by Bowditch. More recently, continuous families of pairwise non-quasi-isometric groups were constructed inside the classes of solvable groups (Cornulier-Tessera), groups with property FP (Kropholler-Leary-Soroko), and Gromov monsters (Gruber-Sisto). I will explain that all these results can be thought of as particular manifestations of a more general phenomenon, which has its roots in descriptive set theory. We will also discuss applications of this approach to constructing new examples of non-quasi-isometric groups having interesting algebraic and geometric properties.

*October 25, Piotr Nowak (Polish Academy of Sciences)

Title: On property (T) for Aut(Fn)

I will present the proof that Aut(Fn), the automorphism group of the free group on n generators, has Kazhdan’s property (T) for n>4
The proof uses a characterization of property (T) via an algebraic condition in the group ring due to Ozawa. The strategy involves computer assistance in the form of semidefinite programing (i.e. positive definite convex optimization).
As one of the applications we also obtain new asymptotically optimal estimates of Kazhdan constant for Aut(Fn) and SLn(Z).
This is joint work with Marek Kaluba and Taka Ozawa (n=5) and with Kaluba and Dawid Kielak (n>5).

*November 1,  Jean-Camille Birget (Rutgers-Camden)

TitleThe word problem of the Brin-Thompson groups is coNP-complete


We prove that the word problem of the Brin-Thompson group nV over a finite generating set is coNP-complete (for n   2). The groups nV with n   2 are the first examples of finitely presented simple groups with non-easy word problem. Unless NP = coNP, nV (for   2) is not embeddable in a finitely presented group with polynomially bounded Dehn function.

The groups nV were introduced by Matt Brin as an n-dimensional generalization of the Thompson group V , which itself was the first known example of an infinite finitely presented, simple group. It was proved by Brin and others that the groups nV form an infinite family of infinite, finitely presented, simple groups.

We also prove that the word problem of the Thompson group V over a certain infinite set of generators, related to boolean circuits, is coNP-complete. The groups nV (and their monoid generalizations) are a bridge between algebra and models of computation.

The talk is based on the preprint arXiv:1902.03852 (Feb. 2019).


Also happening the week of Oct 28-Nov 1:

*Monday, October 28: CUNY Graduate Center Math Colloquium, 5pm-6pm, Room 4214 (Math Lounge)
Speaker: Ilya Kapovich (Hunter College)
Title:  Counting closed geodesics in the moduli space of Outer space: double exponential growth. 

*Friday, November 1: Special guest lecture, 2pm-3:30pm, Room 3212, Graduate Center
Speaker: Lisa Carbone (Rutgers University)
Title:Simple Lie Groups of Finite and Infinite Dimensions (problems talk for graduate students). 


*November 8, Alfredo Costa (University of Coimbra)

TitleThe profinite Schützenberger group defined by a symbolic dynamical system.


In finite semigroup theory, free profinite semigroups play a very
important role. Around 2005, Almeida introduced a connection with
symbolic dynamics that proved to be helpful to understand their
structure. One of the most relevant aspects of this connection is the
association between an irreducible symbolic dynamical system X and the
Schützenberger group G(X) of a special regular J-class, defined by X, of
the free profinite semigroup over the alphabet of X.

The profinite group G(X) is a dynamical invariant. In the case of
minimal systems, it has a sort of geometric interpretation: it is the
inverse limit of the profinite completions of the fundamental groups of
the finite Rauzy graphs of X.

In this talk, we survey some of the main results about the group G(X),
ending, if time permits, with a recent application to the theory of
codes (arXiv:1811.03185).


*November 15,  Alexander Ushakov (Stevens Institute of Technology)

TitleConjugacy problem in the first Grigorchuk's group

We prove that  Conjugacy problem in the first 
Grigorchuk's group can be solved in linear time.


*November 22,  Robert Gilman (Stevens Institute of Technology)

TitleGeneric-Case Complexity at Age 16

Geometric group theory has many important computational problems, e.g., the word, conjugacy and isomorphism problems, which are uncomputable. Standard techniques from computer science for analysis of algorithms do not apply to these problems; but generic-case complexity does. In this talk we review the development of generic-case complexity since its introduction in 2003 and speculate on solutions to some of its open problems.

The seminar meets Friday 4:00-5:00 p.m. at the Graduate Center of the City University of New York (Room 5417).  
The current organizers are:  

If you would like to give a talk, or have a suggestion for a seminar speaker, please e-mail one of the organizers. If you want to be added to/removed from the NYGT Seminar mailing list, please e-mail Ilya Kapovich at ikapovitch@gmail.com.
You can also subscribe/unsubscribe for the NYGT mailing list directly, at
NYGT mailing list subscribe/unsubscribe page: