A logical limit law for 231-avoiding permutations

DOI10.46298/DMTCS.11751arXiv2210.05537MaRDI QIDQ6506763FDOQ6506763

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

Abstract: We prove that the class of 231-avoiding permutations satisfies a convergence 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 behaviour 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.

Mathematics Subject Classification ID

Combinatorial probability (60C05) Model theory of finite structures (03C13) Asymptotic enumeration (05A16)

This page was built for publication: A logical limit law for $231$-avoiding permutations

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