2016/07/11 by Ivanov, Sergei V.
Computer Science · Mathematics · #20E07 #20F65 #90C90 #Advanced Graph Theory Research #FOS: Mathematics #Geometric and Algebraic Topology #Group Theory (math.GR) #Optimization and Control (math.OC) #Primary 20E06 #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1607.03052
openalex publication_date 2016/07/11 · openalex created_date 2022/10/01 · openalex updated_date 2026/07/28
We study the intersection of finitely generated factor-free subgroups of free\nproducts of groups by utilizing the method of linear programming. For example,\nwe prove that if H1 is a finitely generated factor-free noncyclic subgroup\nof the free product G1 * G2 of two finite groups G1, G2, then the\nWN-coefficient \σ(H1) of H1 is rational and can be computed in\nexponential time in the size of H1. This coefficient \σ(H1) is the\nminimal positive real number such that, for every finitely generated\nfactor-free subgroup H2 of G1 * G2, it is true that rm r (H1,\nH2) \≤ \σ(H1) rm r(H1) rm r(H2), where \ rm\nr (H) = \max ( rm r (H)-1,0) is the reduced rank of H, rm r(H) is\nthe rank of H, and rm r(H1, H2) is the reduced rank of the\ngeneralized intersection of H1 and H2. In the case of the free product\nG1 * G2 of two finite groups G1, G2, it is also proved that there\nexists a factor-free subgroup H2^* = H2^*(H1) such that rm r(H1,\nH2^*) = \σ(H1) rm r(H1) rm r(H2^*), H2^* has at\nmost doubly exponential size in the size of H1, and H2^* can be\nconstructed in exponential time in the size of H1.\n