Search

It is undecidable in general whether a given finitely presented group is word hyperbolic. We use the concept of pregroups, introduced by Stallings, to define a new class of van Kampen diagrams, which represent groups as quotients of virtually free groups. We then present a polynomial-time procedure which analyses these diagrams, and either returns an explicit linear Dehn function for the presentation, or returns fail, together with its reasons for failure. Furthermore, if our procedure succeeds we are often able to produce in polynomial time a word problem solver for the presentation that runs in linear time. Our algorithms have been implemented, and are often many orders of magnitude faster than KBMAG, the only comparable publicly available software., Comment: To appear in Journal of Symbolic Computation

For every pair of positive integers $p > q$ we construct a one-relator group $R_{p,q}$ whose Dehn function is $\simeq n^{2 \alpha}$ where $\alpha = \log_2(2p / q)$. The group $R_{p,q}$ has no subgroup isomorphic to a Baumslag-Solitar group $BS(m,n)$ with $m \neq \pm n$, but is not automatic, not CAT(0), and cannot act freely on a CAT(0) cube complex. This answers a long-standing question on the automaticity of one-relator groups and gives counterexamples to a conjecture of Wise., Comment: 6 pages, 1 figure; v3 final version to appear in Proceedings of the American Mathematical Society; v2 correct remark about residual finiteness

We investigate groups whose Cayley graphs have poor\-ly connected subgraphs. We prove that a finitely generated group has bounded separation in the sense of Benjamini--Schramm--Tim\'ar if and only if it is virtually free. We then prove a gap theorem for connectivity of finitely presented groups, and prove that there is no comparable theorem for all finitely generated groups. Finally, we formulate a connectivity version of the conjecture that every group of type $F$ with no Baumslag-Solitar subgroup is hyperbolic, and prove it for groups with at most quadratic Dehn function., Comment: 14 pages. Changes to v2: Proof of the Theorem 1.2 shortened, Theorem 1.4 added completing the no-gap result outlined in v1

We introduce the notion of metrically systolic simplicial complexes. We study geometric and large-scale properties of such complexes and of groups acting on them geometrically. We show that all two-dimensional Artin groups act geometrically on metrically systolic complexes. As direct corollaries we obtain new results on two-dimensional Artin groups and all their finitely presented subgroups: we prove that the Conjugacy Problem is solvable, and that the Dehn function is quadratic. We also show several large-scale features of finitely presented subgroups of two-dimensional Artin groups, lying background for further studies concerning their quasi-isometric rigidity., Comment: final preprint version, to appear in Math. Ann

The isoperimeric spectrum consists of all real positive numbers $\alpha$ such that $O(n^\alpha)$ is the Dehn function of a finitely presented group. In this note we show how a recent result of Olshanskii completes the description of the isoperimetric spectrum modulo the celebrated Computer Science conjecture (and one of the seven Millennium Problems) $\mathbf{P=NP}$ and even a formally weaker conjecture., Comment: 3 pages

We show that the Dehn function of the handlebody group is exponential in any genus $g\geq 3$. On the other hand, we show that the handlebody group of genus $2$ is cubical, biautomatic, and therefore has a quadratic Dehn function., 29 pages, 8 figures

It is shown that D. Cohen's inequality bounding the isoperimetric function of a group by the double exponential of its isodiametric function is valid in the more general context of locally finite simply connected complexes. It is shown that in this context this bound is ‘best possible’. Also studied are second-dimensional isoperimetric functions for groups and complexes. It is shown that the second-dimensional isoperimetric function of a group is bounded by a recursive function. By a similar argument it is shown that the area distortion of a finitely presented subgroup of a finitely presented group is recursive. Cohen's inequality is extended to second-dimensional isoperimetric and isodiametric functions of 2-connected simplicial complexes.

Stackability for finitely presented groups consists of a dynamical system that iteratively moves paths into a maximal tree in the Cayley graph. Combining with formal language theoretic restrictions yields auto- or algorithmic stackability, which implies solvability of the word problem. In this paper we give two new characterizations of the stackable property for groups, and use these to show that every HNN extension of a stackable group is stackable. We apply this to exhibit a wide range of Dehn functions that are admitted by stackable and autostackable groups, as well as an example of a stackable group with unsolvable word problem. We use similar methods to show that there exist finitely presented metabelian groups that are non-constructible but admit an autostackable structure., 34 pages

It is conjectured that a hyperbolic knot admits at most three Dehn surgeries which yield closed three manifolds containing incompressible tori. We show that there exist infinitely many hyperbolic knots which attain the conjectural maximum number. Interestingly, those surgeries correspond to consecutive integers., Comment: 10 pages, 10 figures

We construct a family of trivial [Formula: see text]-knots [Formula: see text] in [Formula: see text] such that the maximal complexity of [Formula: see text]-knots in any isotopy connecting [Formula: see text] with the standard unknot grows faster than a tower of exponentials of any fixed height of the complexity of [Formula: see text]. Here, we can either construct [Formula: see text] as smooth embeddings and measure their complexity as the ropelength (a.k.a the crumpledness) or construct PL-knots [Formula: see text], consider isotopies through PL knots, and measure the complexity of a PL-knot as the minimal number of flat [Formula: see text]-simplices in its triangulation. These results contrast with the situation of classical knots in [Formula: see text], where every unknot can be untied through knots of complexity that is only polynomially higher than the complexity of the initial knot.

Let X be a product of r locally compact and geodesically complete Hadamard spaces. We prove that the horospheres in X centered at regular boundary points of X are Lipschitz-(r − 2)-connected. If X has finite Assouad–Nagata dimension, then using the filling construction by R. Young in [10] this gives sharp bounds on higher order Dehn functions for such horospheres. Moreover, if Γ ⊂ Is(X) is a lattice acting cocompactly on X minus a union of disjoint horoballs, then we get a sharp bound on higher order Dehn functions for Γ. We deduce that apart from the Hilbert modular groups already considered by R. Young, every irreducible ℚ-rank one lattice acting on a product of r Riemannian symmetric spaces of the noncompact type is undistorted up to dimension r−1 and has k-th order Dehn function asymptotic to V (k+1)/k for all k ≤ r − 2.

Pride groups are defined by means of finite (simplicial) graphs, and examples include Artin groups, Coxeter groups, and generalized tetrahedron groups. Under suitable conditions, we calculate an upper bound of the first order Dehn function for a finitely presented Pride group. We thus obtain sufficient conditions for when finitely presented Pride groups have solvable word problems. As a corollary to our main result, we show that the first order Dehn function of a generalized tetrahedron group, containing finite generalized triangle groups, is at most cubic.

Given a knot K in the three-sphere, we address the question: which Dehn surgeries on K bound negative-definite four-manifolds? We show that the answer depends on a number m(K), which is a smooth concordance invariant. We study the properties of this invariant, and compute it for torus knots., Comment: 16 pages, 5 figures

The homological and homotopical Dehn functions are different ways of measuring the difficulty of filling a closed curve inside a group or a space. The homological Dehn function measures fillings of cycles by chains, while the homotopical Dehn function measures fillings of curves by disks. Since the two definitions involve different sorts of boundaries and fillings, there is no a priori relationship between the two functions, but prior to this work there were no known examples of finitely-presented groups for which the two functions differ. This paper gives the first such examples, constructed by amalgamating a free-by-cyclic group with several Bestvina-Brady groups., (17 pages)

This paper shows that a finitely presented monoid with linear Dehn function need not have a regular cross-section, strengthening the previously-known result that such a monoid need not be presented by a finite complete string rewriting system, and contrasting the fact that finitely presented groups with linear Dehn function always have regular cross-sections., 13 pages; 1 table

We show that the mapping class group of a handlebody of genus at least 2 has a Dehn function of at most exponential growth type., 21 pages, 1 figure

Let Y be a compact, oriented 3-manifold with a contact form a. For any Dirac operator D, we study the asymptotic behavior of the spectral flow between D and D+cl(-ira) as r very large. If a is the Thurston-Winkelnkemper contact form whose monodromy is the product of Dehn twists along disjoint circles, we prove that the next order term of the spectral flow function is of order r., Various typos corrected

We construct a finitely presented group with undecidable word problem and with Dehn function bounded by a quadratic function on an infinite set of positive integers., 108 pages, 24 figures

We prove that the Word Problem in the Baumslag group G ( 1 , 2 ) = 〈 a , b ; a a b = a 2 〉 which has a non-elementary Dehn function is decidable in polynomial time.

We survey results about computational complexity of the word problem in groups, Dehn functions of groups and related problems., Comment: 86 pages. Preliminary version, comments are welcome. v2: some references added, misprints fixed, some changes suggested by the readers are made. 88 pages. v3: more readers' suggestions implemented, index added, the list of references improved. This version is submitted to a journal. v4: The paper is accepted in Bulletin of Mathematical Sciences

We study the algebraic and geometric structures for closed orientable 3 -manifolds obtained by Dehn surgery along the family of hyperbolic links with certain surgery coefficients and moreover, the geometric presentations of the fundamental group of these manifolds. We prove that our surgery manifolds are 2 -fold cyclic covering of 3 -sphere branched over certain link by applying the Montesinos theorem in Montesinos-Amilibia (1975). In particular, our result includes the topological classification of the closed 3 -manifolds obtained by Dehn surgery on the Whitehead link, according to Mednykh and Vesnin (1998), and the hyperbolic link 𝐿 𝑑 + 1 of 𝑑 + 1 components in Cavicchioli and Paoluzzi (2000).

Motivated by a question of B. Wajnryb we construct embeddings of the braid group in mapping class groups of surfaces, which are not geometric in the sense that the images of standard generators are not Dehn twists. Our construction uses non-orientable sur- faces and the fact that the mapping class group of such a surface embeds via lifting of homeomorphisms in the mapping class group of its orientable double cover.

We show that there is no algorithm deciding whether the maximal residually free quotient of a given finitely presented group is finitely presentable or not. Given a finitely generated subgroup G of a finite product of limit groups, we discuss the possibility of finding an explicit set of defining equations (i.e. of expressing G as the maximal residually free quotient of an explicit finitely presented group)., Comment: 5 pages. Updated reference

We prove that groups in a certain class of metabelian locally compact groups, have quadratic Dehn function. As an application, we embed the solvable Baumslag-Solitar groups into finitely presented metabelian groups with quadratic Dehn function. Also, we prove that Baumslag's finitely presented metabelian groups, in which the lamplighter groups embed, have quadratic Dehn function., 13 pages, one figure. v1->v2: title has been changed; added application to Baumslag's group v2->v3 numerous corrections

Viewing Dehn's algorithm as a rewriting system, we generalise to allow an alphabet containing letters which do not necessarily represent group elements. This extends the class of groups for which the algorithm solves the word problem to include nilpotent groups, many relatively hyperbolic groups including geometrically finite groups and fundamental groups of certain geometrically decomposable manifolds. The class has several nice closure properties. We also show that if a group has an infinite subgroup and one of exponential growth, and they commute, then it does not admit such an algorithm. We dub these Cannon's algorithms., Comment: 33 pages, 2 figures, credits Kambites and Otto, mentions new work in progress