## Abstract

We study the intersection of finitely generated subgroups of free groups by utilizing the method of linear programming. We prove that if H_{1} is a finitely generated subgroup of a free group F, then the WN-coefficient σ(H_{1}) of H_{1} is rational and can be computed in deterministic exponential time in the size of H_{1}. This coefficient σ(H_{1}) is the minimal nonnegative real number such that, for every finitely generated subgroup H_{2} of F, it is true that r ¯ (H_{1}, H_{2}) ≤ σ(H_{1}) r ¯ (H_{1}) r ¯ (H_{2}) , where r ¯ (H) : = max (r (H) - 1 , 0) is the reduced rank of H, r (H) is the rank of H, and r ¯ (H_{1}, H_{2}) is the reduced rank of the generalized intersection of H_{1} and H_{2}. 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 H_{1} and Γ(H2∗) can be constructed in exponential time in the size of H_{1}.

Original language | English (US) |
---|---|

Pages (from-to) | 1909-1940 |

Number of pages | 32 |

Journal | Mathematische Annalen |

Volume | 370 |

Issue number | 3-4 |

DOIs | |

State | Published - Apr 1 2018 |

## Keywords

- 20E07
- 20F65
- 90C90
- Primary 20E05
- Secondary 68Q25

## ASJC Scopus subject areas

- General Mathematics