Paperlane

no. 3 · Tuesday 27 October 2026

On first-order limiting probabilities for small permutation classes

Victor Falgas-Ravry, Klas Markström, Eero Räty and Fiona Skerman

math.CO

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.

fields
Combinatorics
pdf ↗ page arXiv:2610.34328 ↗