Source author record

Enric Ventura

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.GR Discrete Mathematics math.CO

Catalog footprint

Research overview

15works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2023arXiv

Autòmats de Stallings, un camí d'anada i tornada

In this paper we review some of the fundamental properties of the free group and give a detailed account of Stallings's theory of automata, a geometric interpretation of its subgroups that has been (and still is) immensely fruitful, both as a means of understanding classical results, as as a source of new results. We review some of the most important ones. -- - En aquest article revisem algunes de les propietats fonamentals del group lliure i fem una exposició detallada de la teoria dels autòmats de Stallings, una interpretació geomètrica dels seus subgrups que ha estat (i segueix essent) immensament fructífera, tant com a mitjà per entendre resultats clàssics, com com a font de nous resultats. N'expliquem alguns dels més rellevants.

preprint2022arXiv

A list of applications of Stallings automata

This survey is intended to be a fast (and reasonably updated) reference for the theory of Stallings automata and its applications to the study of subgroups of the free group, with the main accent on algorithmic aspects. Consequently, results concerning finitely generated subgroups have greater prominence in the paper. However, when possible, we try to state the results with more generality, including the usually overlooked non-(finitely-generated) case.

preprint2022arXiv

Stallings automata for free-times-abelian groups: intersections and index

We extend the classical Stallings theory (describing subgroups of free groups as automata) to direct products of free and abelian groups: after introducing enriched automata (i.e., automata with extra abelian labels), we obtain an explicit bijection between subgroups and a certain type of such enriched automata, which - as it happens in the free group - is computable in the finitely generated case. This approach provides a neat geometric description of (even non finitely generated) intersections of finitely generated subgroups within this non-Howson family. In particular, we give a geometric solution to the subgroup intersection problem and the finite index problem, providing recursive bases and transversals respectively.

preprint2020arXiv

Degrees of compression and inertia for free-abelian times free groups

We introduce the concepts of degree of inertia, $\text{di}_G(H)$ , and degree of compression, $\text{dc}_G(H)$ , of a finitely generated subgroup $H$ of a given group $G$ . For the case of direct products of free-abelian and free groups, we compute the degree of compression and give an upper bound for the degree of inertia. Imposing some technical assumptions to the supremum involved in the definition of degree of inertia, we introduce the notion called restricted degree of inertia, $\text{di}'_G(H)$ , and, again for the case $\mathbb{Z}^m \times F_n$ , we provide an explicit formula relating it to the restricted degree of inertia of its projection to the free part, $\text{di}'_{F_n}(Hπ)$ .

preprint2016arXiv

Algorithmic recognition of infinite cyclic extensions

We prove that one cannot algorithmically decide whether a finitely presented $\mathbb{Z}$ -extension admits a finitely generated base group, and we use this fact to prove the undecidability of the BNS invariant. Furthermore, we show the equivalence between the isomorphism problem within the subclass of unique $\mathbb{Z}$ -extensions, and the semi-conjugacy problem for deranged outer automorphisms.

preprint2015arXiv

Bounding the gap between a free group (outer) automorphism and its inverse

For any finitely generated group $G$ , two complexity functions $α_G$ and $β_G$ are defined to measure the maximal possible gap between the norm of an automorphism (respectively outer automorphism) of $G$ and the norm of its inverse. Restricting attention to free groups $F_r$ , the exact asymptotic behaviour of $α_2$ and $β_2$ is computed. For rank $r\geqslant 3$ , polynomial lower bounds are provided for $α_r$ and $β_r$ , and the existence of a polynomial upper bound is proved for $β_r$ .

preprint2015arXiv

Degree of commutativity of infinite groups

We prove that, in a finitely generated residually finite group of subexponential growth, the proportion of commuting pairs is positive if and only if the group is virtually abelian. In particular, this covers the case where the group has polynomial growth (i.e., virtually nilpotent groups, where the hypothesis of residual finiteness is always satisfied). We also show that, for non-elementary hyperbolic groups, the proportion of commuting pairs is always zero.

preprint2015arXiv

Fixed subgroups are compressed in surface groups

For a compact surface $Σ$ (orientable or not, and with boundary or not) we show that the fixed subgroup, $\operatorname{Fix} B$ , of any family $B$ of endomorphisms of $π_1(Σ)$ is compressed in $π_1(Σ)$ i.e., $\operatorname{rk}((\operatorname{Fix} B)\cap H)\leq \operatorname{rk}(H)$ for any subgroup $\operatorname{Fix} B \leq H \leq π_1(Σ)$ . On the way, we give a partial positive solution to the inertia conjecture, both for free and for surface groups. We also investigate direct products, $G$ , of finitely many free and surface groups, and give a characterization of when $G$ satisfies that $\operatorname{rk}(\operatorname{Fix} ϕ) \leq \operatorname{rk}(G)$ for every $ϕ\in Aut(G)$ .

preprint2013arXiv

Orbit decidability, applications and variations

We present the notion of orbit decidability into a more general framework, exploring interesting generalizations and variations of this algorithmic problem. A recent theorem by Bogopolski-Martino-Ventura gave a renovated protagonism to this notion and motivated several interesting algebraic applications.

preprint2013arXiv

The conjugacy problem in extensions of Thompson's group F

We solve the twisted conjugacy problem on Thompson's group F. We also exhibit orbit undecidable subgroups of Aut(F), and give a proof that Aut(F) and Aut_+(F) are orbit decidable provided a certain conjecture on Thompson's group T is true. By using general criteria introduced by Bogopolski, Martino and Ventura in [5], we construct a family of free extensions of F where the conjugacy problem is unsolvable. As a byproduct of our techniques, we give a new proof of a result of Bleak-Fel'shtyn-Goncalves in [4] showing that F has property R_\infty, and which can be extended to show that Thompson's group T also has property R_\infty.

preprint2012arXiv

A Whitehead algorithm for toral relatively hyperbolic groups

We prove that there is an algorithm to determine whether a tuple of elements in a toral relatively hyperbolic group G is in the automorphic orbit of the other tuple.

preprint2012arXiv

The conjugacy problem in automaton groups is not solvable

(Free-abelian)-by-free, self-similar groups generated by finite self-similar sets of tree automorphisms and having unsolvable conjugacy problem are constructed. Along the way, orbit undecidable, free subgroups of GL_d(Z), for d > 5, and Aut(F_d), for d > 4, are constructed as well.

preprint2011arXiv

Finite automata for Schreier graphs of virtually free groups

The Stallings construction for finitely generated subgroups of free groups is generalized by introducing the concept of Stallings section, which allows an eficient computation of the core of a Schreier graph based on edge folding. It is proved that those groups admitting Stallings sections are precisely finitely generated virtually free groups, through a constructive approach based on Bass-Serre theory. Complexity issues and applications are also discussed.

preprint2011arXiv

Statistical properties of subgroups of free groups

The usual way to investigate the statistical properties of finitely generated subgroups of free groups, and of finite presentations of groups, is based on the so-called word-based distribution: subgroups are generated (finite presentations are determined) by randomly chosen k-tuples of reduced words, whose maximal length is allowed to tend to infinity. In this paper we adopt a different, though equally natural point of view: we investigate the statistical properties of the same objects, but with respect to the so-called graph-based distribution, recently introduced by Bassino, Nicaud and Weil. Here, subgroups (and finite presentations) are determined by randomly chosen Stallings graphs whose number of vertices tends to infinity. Our results show that these two distributions behave quite differently from each other, shedding a new light on which properties of finitely generated subgroups can be considered frequent or rare. For example, we show that malnormal subgroups of a free group are negligible in the graph-based distribution, while they are exponentially generic in the word-based distribution. Quite surprisingly, a random finite presentation generically presents the trivial group in this new distribution, while in the classical one it is known to generically present an infinite hyperbolic group.

preprint2011arXiv

Twisted conjugacy in braid groups

In this note we solve the twisted conjugacy problem for braid groups, i.e. we propose an algorithm which, given two braids $u,v\in B_n$ and an automorphism $ϕ\in Aut (B_n)$ , decides whether $v=(ϕ(x))^{-1}ux$ for some $x\in B_n$ . As a corollary, we deduce that each group of the form $B_n \rtimes H$ , a semidirect product of the braid group $B_n$ by a torsion-free hyperbolic group $H$ , has solvable conjugacy problem.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Enric Ventura

Research overview

Is this your work?

15 publications

Autòmats de Stallings, un camí d'anada i tornada

A list of applications of Stallings automata

Stallings automata for free-times-abelian groups: intersections and index

Degrees of compression and inertia for free-abelian times free groups

Algorithmic recognition of infinite cyclic extensions

Bounding the gap between a free group (outer) automorphism and its inverse

Degree of commutativity of infinite groups

Fixed subgroups are compressed in surface groups

Orbit decidability, applications and variations

The conjugacy problem in extensions of Thompson's group F

A Whitehead algorithm for toral relatively hyperbolic groups

The conjugacy problem in automaton groups is not solvable

Finite automata for Schreier graphs of virtually free groups

Statistical properties of subgroups of free groups

Twisted conjugacy in braid groups

See the researcher in context

Building this map preview