# Groups, Geometry, and Dynamics

Volume 11, Issue 4, 2017, pp. 1113–1177
DOI: 10.4171/GGD/424

Published online: 2017-12-07

Linear programming and the intersection of free subgroups in free products of groups

Sergei V. Ivanov[1]

(1) University of Illinois-Urbana Champaign, USA

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 * 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 * G_2$, it is true that $\bar {\mathrm r}(H_1, H_2) \le \sigma(H_1) \bar {\mathrm r}(H_1) \bar {\mathrm r}(H_2)$, where $\bar{ {\mathrm r}} (H)$ = max (r $(H)-1,0)$ is the reduced rank of $H$, 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 * G_2$ of two finite groups $G_1$, $G_2$, it is also proved that there exists a factor-free subgroup $H_2^* = H_2^*(H_1)$ such that $\bar {\mathrm r}(H_1, H_2^*) = \sigma(H_1) \bar {\mathrm r}(H_1)\bar {\mathrm r}(H_2^*)$, $H_2^*$ has at most doubly exponential size in the size of $H_1$, and $H_2^*$ can be constructed in exponential time in the size of $H_1$.

Keywords: Free products of groups, free and factor-free subgroups, rank of intersection of factor-free subgroups, linear programming

Ivanov Sergei: Linear programming and the intersection of free subgroups in free products of groups. Groups Geom. Dyn. 11 (2017), 1113-1177. doi: 10.4171/GGD/424