Frédérique Bassino ; Cyril Nicaud ; Pascal Weil - Generic properties of random subgroups of a free group for general distributions

dmtcs:2991 - Discrete Mathematics & Theoretical Computer Science, January 1, 2012, DMTCS Proceedings vol. AQ, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12) - https://doi.org/10.46298/dmtcs.2991
Generic properties of random subgroups of a free group for general distributions

Authors: Frédérique Bassino ORCID-iD; Cyril Nicaud ; Pascal Weil

    We consider a generalization of the uniform word-based distribution for finitely generated subgroups of a free group. In our setting, the number of generators is not fixed, the length of each generator is determined by a random variable with some simple constraints and the distribution of words of a fixed length is specified by a Markov process. We show by probabilistic arguments that under rather relaxed assumptions, the good properties of the uniform word-based distribution are preserved: generically (but maybe not exponentially generically), the tuple we pick is a basis of the subgroup it generates, this subgroup is malnormal and the group presentation defined by this tuple satisfies a small cancellation condition.


    Volume: DMTCS Proceedings vol. AQ, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12)
    Section: Proceedings
    Published on: January 1, 2012
    Imported on: January 31, 2017
    Keywords: [MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO],[MATH.MATH-GR] Mathematics [math]/Group Theory [math.GR],[INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS]

    Share

    Consultation statistics

    This page has been seen 165 times.
    This article's PDF has been downloaded 120 times.