Michael Albert ; Mathilde Bouvel ; Valentin Féray ; Marc Noy - A logical limit law for $231$-avoiding permutations

dmtcs:11751 - Discrete Mathematics & Theoretical Computer Science, April 2, 2024, vol. 26:1, Permutation Patterns 2023 - https://doi.org/10.46298/dmtcs.11751
A logical limit law for $231$-avoiding permutationsArticle

Authors: Michael Albert ; Mathilde Bouvel ; Valentin Féray ; Marc Noy

    We prove that the class of 231-avoiding permutations satisfies a logical limit law, i.e. that for any first-order sentence $\Psi$, in the language of two total orders, the probability $p_{n,\Psi}$ that a uniform random 231-avoiding permutation of size $n$ satisfies $\Psi$ admits a limit as $n$ is large. Moreover, we establish two further results about the behavior and value of $p_{n,\Psi}$: (i) it is either bounded away from $0$, or decays exponentially fast; (ii) the set of possible limits is dense in $[0,1]$. Our tools come mainly from analytic combinatorics and singularity analysis.


    Volume: vol. 26:1, Permutation Patterns 2023
    Section: Special issues
    Published on: April 2, 2024
    Accepted on: December 22, 2023
    Submitted on: August 22, 2023
    Keywords: Mathematics - Combinatorics,Mathematics - Probability,05A16, 60C05 (primary), 03C13 (secondary)

    Consultation statistics

    This page has been seen 295 times.
    This article's PDF has been downloaded 177 times.