TY - JOUR
T1 - The intersection of subgroups in free groups and linear programming
AU - Ivanov, S. V.
N1 - Funding Information:
Supported in smaller part by the NSF under Grant DMS 09-01782.
Publisher Copyright:
© 2017, Springer-Verlag GmbH Deutschland.
PY - 2018/4/1
Y1 - 2018/4/1
N2 - We study the intersection of finitely generated subgroups of free groups by utilizing the method of linear programming. We prove that if H1 is a finitely generated subgroup of a free group F, then the WN-coefficient σ(H1) of H1 is rational and can be computed in deterministic exponential time in the size of H1. This coefficient σ(H1) is the minimal nonnegative real number such that, for every finitely generated subgroup H2 of F, it is true that r ¯ (H1, H2) ≤ σ(H1) r ¯ (H1) r ¯ (H2) , where r ¯ (H) : = max (r (H) - 1 , 0) is the reduced rank of H, r (H) is the rank of H, and r ¯ (H1, H2) is the reduced rank of the generalized intersection of H1 and H2. We also show the existence of a subgroup H2∗=H2∗(H1) of F such that r¯(H1,H2∗)=σ(H1)r¯(H1)r¯(H2∗), the Stallings graph Γ(H2∗) of H2∗ has at most doubly exponential size in the size of H1 and Γ(H2∗) can be constructed in exponential time in the size of H1.
AB - We study the intersection of finitely generated subgroups of free groups by utilizing the method of linear programming. We prove that if H1 is a finitely generated subgroup of a free group F, then the WN-coefficient σ(H1) of H1 is rational and can be computed in deterministic exponential time in the size of H1. This coefficient σ(H1) is the minimal nonnegative real number such that, for every finitely generated subgroup H2 of F, it is true that r ¯ (H1, H2) ≤ σ(H1) r ¯ (H1) r ¯ (H2) , where r ¯ (H) : = max (r (H) - 1 , 0) is the reduced rank of H, r (H) is the rank of H, and r ¯ (H1, H2) is the reduced rank of the generalized intersection of H1 and H2. We also show the existence of a subgroup H2∗=H2∗(H1) of F such that r¯(H1,H2∗)=σ(H1)r¯(H1)r¯(H2∗), the Stallings graph Γ(H2∗) of H2∗ has at most doubly exponential size in the size of H1 and Γ(H2∗) can be constructed in exponential time in the size of H1.
KW - 20E07
KW - 20F65
KW - 90C90
KW - Primary 20E05
KW - Secondary 68Q25
UR - http://www.scopus.com/inward/record.url?scp=85032971719&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85032971719&partnerID=8YFLogxK
U2 - 10.1007/s00208-017-1595-2
DO - 10.1007/s00208-017-1595-2
M3 - Article
AN - SCOPUS:85032971719
SN - 0025-5831
VL - 370
SP - 1909
EP - 1940
JO - Mathematische Annalen
JF - Mathematische Annalen
IS - 3-4
ER -