On first-order limiting probabilities for small permutation classes

arXiv:2610.34328 · math.CO · Submitted 2026-10-25 · Read on arXiv

math.CO

Submitted: 2026-10-25

Updated: 2026-10-25

License: http://creativecommons.org/licenses/by/4.0/

The gist: Given a small permutation class P, we consider the set of possible limits of the probability P (σ n Ψ) that a uniformly chosen random permutation σ n in P n satisfies a fixed first-order sentence…

Abstract

Given a small permutation class P, we consider the set of possible limits of the probability P (σ n Ψ) that a uniformly chosen random permutation σ n in 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.

Related papers