Linear programming and the intersection of subgroups in free groups

Sergei V. Ivanov

Published 2016-07-28Version 1

We study the intersection of finitely generated subgroups of free groups by utilizing the method of linear programming. We prove that if $H_1$ is a finitely generated subgroup of a free group $F$, then the Walter Neumann coefficient $\sigma(H_1)$ of $H_1$ is rational and can be computed in deterministic exponential time of size of $H_1$. This coefficient $\sigma(H_1)$ is a minimal nonnegative real number such that, for every finitely generated subgroup $H_2$ of $F$, it is true that $\bar{ {\rm r}}(H_1, H_2) \le \sigma(H_1) \bar{ {\rm r}}(H_1) \bar{ {\rm r}}(H_2)$, where $\bar{ {\rm r}} (H) := \max ( {\rm r} (H)-1,0)$ is the reduced rank of $H$, ${\rm r}(H)$ is the rank of $H$, and $\bar{ {\rm r}}(H_1, H_2)$ is the reduced rank of a generalized intersection of $H_1, H_2$.