Linear programming and the intersection of free subgroups in free products of groups (Q1691957)

Summary: We study the intersection of finitely generated factor-free subgroups of free products of groups by utilizing the method of linear programming. For example, we prove that if \(H_1\) is a finitely generated factor-free noncyclic subgroup of the free product \(G_1\ast G_2\) of two finite groups \(G_1\), \(G_2\), then the WN-coefficient \(\sigma(H_1)\) of \(H_1\) is rational and can be computed in exponential time in the size of \(H_1\). This coefficient \(\sigma(H_1)\) is the minimal positive real number such that, for every finitely generated factor-free subgroup \(H_2\) of \(G_1\ast G_2\), it is true that \(\bar{\mathrm{r}}(H_1,H_2)\leq\sigma(H_1)\bar{\mathrm{r}}(H_1)\bar{\mathrm{r}}(H_2)\), where \(\bar{\mathrm{r}}(H)=\max(\mathrm{r}(H)-1,0)\) is the reduced rank of \(H\), \(\mathrm{r}(H)\) is the rank of \(H\), and \(\bar{\mathrm{r}}(H_1,H_2)\) is the reduced rank of the generalized intersection of \(H_1\) and \(H_2\). In the case of the free product \(G_1\ast G_2\) of two finite groups \(G_1,G_2\), it is also proved that there exists a factor-free subgroup \(H_2^\ast=H_2^\ast(H_1)\) such that \(\bar{\mathrm{r}}(H_1,H_2^\ast)=\sigma(H_1)\bar{\mathrm{r}}(H_1)\bar{\mathrm{r}}(H_2^\ast),H_2^\ast\) has at most doubly exponential size in the size of \(H_1\), and \(H_2^\ast\) can be constructed in exponential time in the size of \(H_1\).