zbMATH — the first resource for mathematics

Positively generated subgroups of free groups and the Hanna Neumann conjecture. (English) Zbl 1013.20018
Cleary, Sean (ed.) et al., Combinatorial and geometric group theory. Proceedings of the AMS special session on combinatorial group theory, New York, NY, USA, November 4-5, 2000 and the AMS special session on computational group theory, Hoboken, NJ, USA, April 28-29, 2001. Providence, RI: American Mathematical Society (AMS). Contemp. Math. 296, 155-170 (2002).
The now almost 50 year old Hanna Neumann conjecture on the rank of the intersection of two finitely generated subgroups of a finitely generated free group is treated here with a new idea, namely to use graph-theoretic properties and translate them back to the group-theoretic problem. In particular, a strong directed trail decomposition of a directed graph is defined, in analogy to Whitney’s ear decomposition in the undirected case. This decomposition is used to obtain inductive arguments about properties of positively generated subgroups of free groups, i.e. subgroups generated by a set of words without negative exponents of generators. It is shown that strong connectivity of a subgroup’s folding corresponds exactly to the property that the subgroup is positively generated. The decomposition techniques are then used to show that the Hanna Neumann conjecture holds for pairs of subgroups if one of them is positively generated. Moreover, an algorithm is presented to decide whether or not a finitely generated subgroup is positively generated with respect to a given basis for the ambient group, and yields a positive basis for the subgroup in polynomial time. A basis free approach is suggested and corresponding open problems formulated.
For the entire collection see [Zbl 0990.00044].

20E05 Free nonabelian groups
20F10 Word problems, other decision problems, connections with logic and automata (group-theoretic aspects)
05C25 Graphs and abstract algebra (groups, rings, fields, etc.)
20F05 Generators, relations, and presentations of groups