Mathematics – Group Theory
Scientific paper
2007-07-21
International Journal of Algebra and Computation 18 (2008) 1-31
Mathematics
Group Theory
Scientific paper
We give an efficient algorithm to randomly generate finitely generated subgroups of a given size, in a finite rank free group. Here, the size of a subgroup is the number of vertices of its representation by a reduced graph such as can be obtained by the method of Stallings foldings. Our algorithm randomly generates a subgroup of a given size n, according to the uniform distribution over size n subgroups. In the process, we give estimates of the number of size n subgroups, of the average rank of size n subgroups, and of the proportion of such subgroups that have finite index. Our algorithm has average case complexity $\O(n)$ in the RAM model and $\O(n^2\log^2n)$ in the bitcost model.
Bassino Frédérique
Nicaud Cyril
Weil Pascal
No associations
LandOfFree
Random generation of finitely generated subgroups of a free group does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Random generation of finitely generated subgroups of a free group, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Random generation of finitely generated subgroups of a free group will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-59213