On first-order limiting probabilities for small permutation classes
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
- Three-ends Furstenberg estimates and approximate rectangles
- Multicolor Ramsey numbers of ordered matchings
- Exponential random graph models with soft clique constraints
- A Full-Sequence Quantitative Gap Between the Chromatic and Cochromatic Numbers of a Random Graph
- Ehrhart positivity for paving positroids
- Nonlinear lower-tail large deviations at criticality