JournalsggdVol. 11, No. 4pp. 1113–1177

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

  • Sergei V. Ivanov

    University of Illinois-Urbana Champaign, USA
Linear programming and the intersection of free subgroups in free products of groups cover

A subscription is required to access this article.

Abstract

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 H1H_1 is a finitely generated factor-free noncyclic subgroup of the free product G1G2G_1 * G_2 of two finite groups G1G_1, G2G_2, then the WN-coefficient σ(H1)\sigma(H_1) of H1H_1 is rational and can be computed in exponential time in the size of H1H_1. This coefficient σ(H1)\sigma(H_1) is the minimal positive real number such that, for every finitely generated factor-free subgroup H2H_2 of G1G2G_1 * G_2, it is true that rˉ(H1,H2)σ(H1)rˉ(H1)rˉ(H2)\bar {\mathrm r}(H_1, H_2) \le \sigma(H_1) \bar {\mathrm r}(H_1) \bar {\mathrm r}(H_2), where rˉ(H)\bar{ {\mathrm r}} (H) = max (r (H)1,0)(H)-1,0) is the reduced rank of HH, r(H)(H) is the rank of HH, and rˉ(H1,H2)\bar {\mathrm r}(H_1, H_2) is the reduced rank of the generalized intersection of H1H_1 and H2H_2. In the case of the free product G1G2G_1 * G_2 of two finite groups G1G_1, G2G_2, it is also proved that there exists a factor-free subgroup H2=H2(H1)H_2^* = H_2^*(H_1) such that rˉ(H1,H2)=σ(H1)rˉ(H1)rˉ(H2)\bar {\mathrm r}(H_1, H_2^*) = \sigma(H_1) \bar {\mathrm r}(H_1)\bar {\mathrm r}(H_2^*), H2H_2^* has at most doubly exponential size in the size of H1H_1, and H2H_2^* can be constructed in exponential time in the size of H1H_1.

Cite this article

Sergei V. Ivanov, Linear programming and the intersection of free subgroups in free products of groups. Groups Geom. Dyn. 11 (2017), no. 4, pp. 1113–1177

DOI 10.4171/GGD/424