The intersection of subgroups in free groups and linear programming

Applications of mathematical programming (90C90) Analysis of algorithms and problem complexity (68Q25) Free nonabelian groups (20E05) Generators, relations, and presentations of groups (20F05) Subgroup theorems; subgroup growth (20E07)

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

s i g m a (H_{1})

of

H_{1}

is rational and can be computed in deterministic exponential time in the size of

H_{1}

. This coefficient

s i g m a (H_{1})

is the minimal nonnegative real number such that, for every finitely generated subgroup

H_{2}

of

F

, it is true that

, where

is the reduced rank of

H

,

m r (H)

is the rank of

H

, and

is the reduced rank of the generalized intersection of

H_{1}

and

H_{2}

. We also show the existence of a subgroup

H_{2}^{*} = H_{2}^{*} (H_{1})

of

F

such that

, the Stallings graph

G a m m a (H_{2}^{*})

of

H_{2}^{*}

has at most doubly exponential size in the size of

H_{1}

and

G a m m a (H_{2}^{*})

can be constructed in exponential time in the size of

H_{1}

.

Recommendations

Cites work

Cited in

(5)

This page was built for publication: The intersection of subgroups in free groups and linear programming

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1709789)