The Grushko decomposition of a finite graph of finite rank free groups: an algorithm

Diao, Guo-An¹ ; Feighn, Mark²

¹ School of Arts and Sciences, Holy Family University, Philadelphia, Pennsylvania 19114, USA
² Department of Mathematics and Computer Science, Rutgers University, Newark, New Jersey 07102, USA

Geometry & topology, Tome 9 (2005) no. 4, pp. 1835-1880.

Résumé

A finitely generated group admits a decomposition, called its Grushko decomposition, into a free product of freely indecomposable groups. There is an algorithm to construct the Grushko decomposition of a finite graph of finite rank free groups. In particular, it is possible to decide if such a group is free.

Détail

DOI : 10.2140/gt.2005.9.1835

Keywords: graph of groups, Grushko decomposition, algorithm, labeled graph

Bibliographie

[1] H Bass, Some remarks on group actions on trees, Comm. Algebra 4 (1976) 1091

[2] M Bestvina, M Feighn, Outer limits, preprint (1994)

[3] M Bestvina, M Feighn, A combination theorem for negatively curved groups, J. Differential Geom. 35 (1992) 85

[4] M Bestvina, M Feighn, Bounding the complexity of simplicial group actions on trees, Invent. Math. 103 (1991) 449

[5] M R Bridson, A Haefliger, Metric spaces of non-positive curvature, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], Springer (1999)

[6] M R Bridson, D T Wise, $\scr V\scr H$ complexes, towers and subgroups of $F\times F$, Math. Proc. Cambridge Philos. Soc. 126 (1999) 481

[7] P Brinkmann, Splittings of mapping tori of free group automorphisms, Geom. Dedicata 93 (2002) 191

[8] D E Cohen, Combinatorial group theory: a topological approach, London Mathematical Society Student Texts 14, Cambridge University Press (1989)

[9] G A Diao, Is a graph of finitely generated free groups free? An algorithm (2003)

[10] M Feighn, M Handel, Mapping tori of free group automorphisms are coherent, Ann. of Math. $(2)$ 149 (1999) 1061

[11] K Fujiwara, P Papasoglu, JSJ-decompositions of finitely presented groups and complexes of groups, Geom. Funct. Anal. 16 (2006) 70

[12] R Geoghegan, M L Mihalik, M Sapir, D T Wise, Ascending HNN extensions of finitely generated free groups are Hopfian, Bull. London Math. Soc. 33 (2001) 292

[13] V Gerasimov, Detecting connectedness of the boundary of a hyperbolic group, preprint (1999)

[14] S M Gersten, On Whitehead's algorithm, Bull. Amer. Math. Soc. $($N.S.$)$ 10 (1984) 281

[15] I A Grushko, On generators of a free product of groups (1940) 169

[16] A Hatcher, Algebraic topology, Cambridge University Press (2002)

[17] W Jaco, D Letscher, J H Rubinstein, Algorithms for essential surfaces in 3–manifolds, from: "Topology and geometry: commemorating SISTAG", Contemp. Math. 314, Amer. Math. Soc. (2002) 107

[18] S Kalajdžievski, Automorphism group of a free group: centralizers and stabilizers, J. Algebra 150 (1992) 435

[19] O Kharlampovich, A Myasnikov, Irreducible affine varieties over a free group I: Irreducibility of quadratic equations and Nullstellensatz, J. Algebra 200 (1998) 472

[20] O Kharlampovich, A G Myasnikov, Effective JSJ decompositions, from: "Groups, languages, algorithms", Contemp. Math. 378, Amer. Math. Soc. (2005) 87

[21] R C Lyndon, P E Schupp, Combinatorial group theory, Classics in Mathematics, Springer (2001)

[22] C F Miller Iii, On group-theoretic decision problems and their classification, Annals of Mathematics Studies 68, Princeton University Press (1971)

[23] E Rips, Z Sela, Cyclic splittings of finitely presented groups and the canonical JSJ decomposition, Ann. of Math. $(2)$ 146 (1997) 53

[24] Z Sela, Diophantine geometry over groups I: Makanin–Razborov diagrams, Publ. Math. Inst. Hautes Études Sci. (2001) 31

[25] J P Serre, Trees, Springer Monographs in Mathematics, Springer (2003)

[26] A Shenitzer, Decomposition of a group with a single defining relation into a free product, Proc. Amer. Math. Soc. 6 (1955) 273

[27] J R Stallings, Topology of finite graphs, Invent. Math. 71 (1983) 551

[28] J R Stallings, Foldings of $G$–trees, from: "Arboreal group theory (Berkeley, CA, 1988)", Math. Sci. Res. Inst. Publ. 19, Springer (1991) 355

[29] G A Swarup, Decompositions of free groups, J. Pure Appl. Algebra 40 (1986) 99

[30] J H C Whitehead, On certain sets of elements in a free group (1936) 48

[31] J H C Whitehead, On equivalent sets of elements in a free group, Ann. of Math. $(2)$ 37 (1936) 782