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

Research output: Contribution to journalArticlepeer-review

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 H1 is a finitely generated factor-free noncyclic subgroup of the free product G1 G2 of two finite groups G1, G2, then the WN-coefficientσH1/ of H1 is rational and can be computed in exponential time in the size of H1. This coefficientσH1/ is the minimal positive real number such that, for every finitely generated factor-free subgroup H2 of G1 G2, it is true that Nr.H1;H2/σH1/Nr.H1/Nr.H2/, where Nr.H/ D max.r.H/ ≤ 1; 0/ is the reduced rank of H, r.H/ is the rank of H, and Nr.H1;H2/ is the reduced rank of the generalized intersection of H1 and H2. In the case of the free product G1 G2 of two finite groups G1, G2, it is also proved that there exists a factor-free subgroup H 2 D H 2σH1/ such that Nr.H1;H 2 / DσH1/Nr.H1/Nr.H 2 /, H 2 has at most doubly exponential size in the size of H1, and H 2 can be constructed in exponential time in the size of H1.

Original languageEnglish (US)
Pages (from-to)1113-1177
Number of pages65
JournalGroups, Geometry, and Dynamics
Volume11
Issue number4
DOIs
StatePublished - 2017

Keywords

  • Free and factor-free subgroups
  • Free products of groups
  • Linear programming
  • Rank of intersection of factor-free subgroups

ASJC Scopus subject areas

  • Geometry and Topology
  • Discrete Mathematics and Combinatorics

Fingerprint Dive into the research topics of 'Linear programming and the intersection of free subgroups in free products of groups'. Together they form a unique fingerprint.

Cite this