Skip to content
DraconiticResearch
Search Sources API
186,086 studies31 sourcesUpdated 9 min ago
PreprintCC BY 4.0arXiv

On first-order limiting probabilities for small permutation classes

  • Victor Falgas-Ravry
  • Klas Markström
  • Eero Räty
  • Fiona Skerman
Open at sourcePDFDOICite

Abstract

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

  1. FOSLS-deRhaNN: native de Rham neural classes for H(div) and H(curl) with applications to first-order system least-squares neural network methods for partial differential equations
    Shun Zhang
    arXivPreprintCC BY 4.0Full textNumerical analysis & scientific computingarXiv
  2. New classes of trace-form permutation polynomials and their compositional inverses
    Kirpa Garg
    arXivPreprintarXiv licenceFull textAlgebra & number theoryarXiv
  3. Limiting laminations and boundary weights for infinite-type mapping classes
    Carolyn Abbott, Phuong Pham
    arXivPreprintCC BY 4.0Full textGeometry & topologyarXiv
  4. Finiteness theorems for Cayley permutation classes
    Giulio Cerbai, Anders Claesson
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  5. Logical isomorphism and logical limit laws for small permutation classes and regular languages
    Klas Markström, Eero Räty
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{falgasravry2026firstorder,
  title = {{On first-order limiting probabilities for small permutation classes}},
  author = {Victor Falgas-Ravry and Klas Markström and Eero Räty and Fiona Skerman},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.34328},
  eprint = {2610.34328},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.34328},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - On first-order limiting probabilities for small permutation classes
AU  - Victor Falgas-Ravry
AU  - Klas Markström
AU  - Eero Räty
AU  - Fiona Skerman
PY  - 2026
DA  - 2026/10/25
PB  - arXiv
DO  - 10.48550/arxiv.2610.34328
UR  - https://arxiv.org/abs/2610.34328
AB  - Given a small permutation class 𝒫, we consider the set of possible limits of the probability ℙ(σ_n ⊨ Ψ) that a uniformly chosen random permutation σ_n∈ 𝒫_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.
ER  -