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].

For the entire collection see [Zbl 0990.00044].

Reviewer: Brigitte Servatius (Worcester)

##### MSC:

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 |