On first-order limiting probabilities for small permutation classes

Source abstract

Given a small permutation class $\mathcal{P}$, we consider the set of possible limits of the probability $\mathbb{P}\big(\mathbfσ_n \models Ψ\big)$ that a uniformly chosen random permutation $\mathbfσ_n\in \mathcal{P}_n$ satisfies a fixed first-order sentence in Theory of Two Orders (TOTO). In the case of small permutation classes with polynomial growth, we show this limit set is finite, and characterize the set explicitly. In particular, we prove that many natural small permutation classes of polynomial growth arising from permutation matrices satisfy a $0$-$1$ convergence law, and have an infinite model. In the case of small permutation classes with exponential growth we show that the limit set is dense in $[0,1]$, thereby extending a result of Albert--Bouvel--Féray--Noy, using different methods, to this range.