betaFeedback

WorksMathematics

On first-order limiting probabilities for small permutation classes

Abstract

Given a small permutation class P\mathcal{P}, we consider the set of possible limits of the probability P(σn⊨Ψ)\mathbb{P}\big(\mathbfσ_n \models Ψ\big) that a uniformly chosen random permutation σn∈Pn\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 00-11 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][0,1], thereby extending a result of Albert–Bouvel–Féray–Noy, using different methods, to this range.

Introduction

One way to characterize the typical features of the elements of some class of combinatorial objects is to draw such an element at random according to some probability measure, and study its properties. In particular, one may ask for the probability that such a randomly chosen element satisfies some property that can be described using a suitable version of first-order logic. Starting from the work of Glebskii, Kogan, Liogon’kii and Talanov [15] and Fagin [13], there have been extensive investigations of logical limit laws for random graph models. The monograph [27] by Spencer gives an excellent overview of the subject.

In this paper, we shall be interested in analogous questions for permutations drawn uniformly at random from a permutation class (that is, from sets of permutations P\mathcal{P} that are closed under taking subpatterns, see § 2 for precise definitions). Such questions have recently received much attention and relatively little is known. The study of first-order logical limit laws for permutations in general was initiated by Foy and Woods [14], who showed that a permutation drawn uniformly at random from Sn\mathfrak{S}_{n} does not satisfy a logical limit law. Their work was a strengthening of earlier work by Kaufmann and Shelah [2] who showed non-convergence for monadic second-order logic. Henceforth, we shall refer to a permutation drawn uniformly at random from a permutation class simply as a random permutation from that class.

In contrast to these older results it has recently been shown that for some non-trivial permutation classes there is a first-order limit law, and for some of them the set of limiting probabilities has also been described. In particular, both of these were established for 231-avoiding permutations in [7], and the first-order limit law was subsequently established for 321-avoiding permutations in [32], which up to isomorphism covers all classes avoiding a single pattern of length 3. Another positive result was given in [12], where it was shown that the class of layered permutations satisfies a limit law. They also conjectured that every proper permutation class satisfies a limit law. Going in another direction, [26] identified for which parameter values the non-uniform Mallows distribution on the set of all permutations has a limit law.

Rather than studying individual permutation classes, the aim of this paper is to consider the entire collection of what are known as small permutation classes. As shown by Marcus and Tardos [24] for every proper permutation class there exists an (upper) growth rate τ≥1\tau\geq 1 so that the number of permutations of order nn in the class grows like (at most) τn+o(n)\tau^{n+o(n)}, with τ=1\tau=1 entailing polynomial growth in nn. It has been known for some time now (see the discussion in the next subsection) that a qualitative shift in the behaviour of permutation classes occurs at the growth rate κ=2.205…\kappa=2.205\ldots, the unique positive root of the polynomial 1+2X2−X31+2X^2-X^3. A permutation class with growth rate smaller than this is called a small permutation class.

In [25] the second and third authors of this paper show that every small permutation class has a bijection to a regular language which also acts as a bijection between the first-order logics on either side. In fact, the encoding and the structural bijection extend to monadic second order logic as well. Together with some further structural knowledge of the regular language, this implies that for every small permutation class, the probability of a first-order property holding for an order nn random permutation from that class converges to a limit as n→∞n\rightarrow \infty. See Theorem 1.1 for more precise statements of these results. This shows that the convergence results from [7] and [32] hold for all small permutation classes, and proves the conjecture from [12] mentioned above for all small permutation classes.

The broad aim of this paper is to determine the set of possible limit probabilities for small permutation classes. For each class of polynomial growth we will show that the limit set is finite, and characterize those for which there is a 00-11 law. In the latter case, we also show that there is an infinite model for the class, analogous to the infinite random graph in Fagin’s work [13]. For small permutation classes with superpolynomial growth we instead show that the set of limiting probabilities is dense in [0,1][0,1]. To properly state our results and set them in their context, a fuller background is necessary; this is covered in the next subsection, with our own contributions described in full in § 1.2.

Background and motivation

Permutation classes

Permutation classes have been extensively studied since the pioneering work of Knuth [23 Section 2.2.1] in the late 1960s. Suppose that a permutation class P\mathcal{P} is proper, in the sense that it is not the class of all permutations. What can one say about the growth-rate of ∣Pn∣=∣P∩Sn∣\vert \mathcal{P} _n\vert =\vert \mathcal{P} \cap\mathfrak{S}_{n}\vert as n→∞n \rightarrow \infty? The collection Sn\mathfrak{S}_{n} of all permutations of [n][n] has size n!n!; however, the celebrated Stanley–Wilf conjecture held that for any proper permutation class the growth is at most exponential in nn. Following work of many authors, notably Alon and Friedgut [9] and Klazar [22], the Stanley–Wilf conjecture was finally proved by Marcus and Tardos [24] in 2004.

Given Marcus and Tardos’s result, we have an exponential upper bound for the size of a proper permutation class. When lim sup⁡n→∞∣Pn∣1/n=lim inf⁡n→∞∣Pn∣1/n\limsup_{n\rightarrow \infty} \vert \mathcal{P} _n\vert^{1/n} = \liminf_{n\rightarrow \infty} \vert \mathcal{P} _n\vert^{1/n} we refer to their common value as the Stanley–Wilf limit or growth rate gr(P)\mathrm{gr}( \mathcal{P} ) of the permutation class P\mathcal{P}.

The Stanley–Wilf limit is conjectured to exist for all permutation classes P\mathcal{P} (see e.g. [31 Conjecture 1.1], though this appears to be an older folklore conjecture). A natural question to ask is then: which values can be attained as the Stanley–Wilf limit of some permutation class? When P\mathcal{P} is the set Av(π)\mathrm{Av}(\pi) of all permutations avoiding the pattern π\pi, the Stanley–Wilf limit exists, by a remark of Arratia [10] in combination with [24], but finding the value is hard even for simple patterns.

Given the difficulty of determining growth rates even for some seemingly simple permutation classes, it is natural to approach the problem from a slightly different angle and ask instead: given a (small) constant c>0c > 0, what can be said about the structural properties of permutation classes with growth-rate less than cc, or to determine whether cc is the Stanley–Wilf limit of some class? Questions of this type have seen significantly more progress than the ones concerned with determining the growth rates. One of the first results in this direction was obtained by Kaiser and Klazar [17], who showed in 2002 that if for some arbitrary nn we have ∣Pn∣<Fn\vert \mathcal{P} _n\vert < F_n, where FnF_n denotes the nn-th Fibonacci number, then ∣Pn∣\vert \mathcal{P} _n\vert grows at most polynomially in nn. Thus for all proper permutation classes P\mathcal{P}, the growth rate gr(P)gr( \mathcal{P} ) is either 00, 11 or at least (1+5)/2(1+\sqrt{5})/2. They also obtained a precise classification of the possible growth rates/Stanley–Wilf limits below 22 (which correspond to certain generalized Fibonacci numbers).

After several improvements [20, 18], a remarkable breakthrough was made by Vatter [29], who showed that a certain type of phase transition occurs at the growth-rate κ≈2.205\kappa \approx 2.205, where κ\kappa is the least positive root of 1+2X2−X31+2X^2-X^3. We say that a permutation class P\mathcal{P} is a small permutation class if gr‾(P)<κ\mathrm{\overline{gr}}(\mathcal{P}) < \kappa. In his influential work, Vatter [29] provided a rather specific structural classification for small permutation classes (which we will state in § 2.3), proved that there are only countably many small permutation classes, and also proved that there are already uncountably many permutation classes with growth-rate precisely κ\kappa and pairwise distinct generating functions.

Other natural phase transitions occurring at higher growth-rates were subsequently identified by Pantone and Vatter [16], and Vatter [30]: Pantone and Vatter [16] determined an explicit constant ξ\xi such that there are only countably many Stanley–Wilf limits below ξ\xi, but such that for every ε>0\varepsilon>0 there are uncountably many Stanley–Wilf limits in every half-open interval [ξ,ξ+ε)[\xi, \xi+\varepsilon). Vatter [30], on the other hand, showed that there exists a constant λ≈2.48\lambda \approx 2.48 such that every real number greater than λ\lambda is the Stanley–Wilf limit of some proper permutation class.

Vatter [29] also conjectured that every small permutation class has a rational generating function. The conjecture was later proved by Albert, Ruškuc, and Vatter [8]; in particular, their result implies that the Stanley–Wilf limit exists for every small permutation class. Recently, the second and third authors gave an alternative proof of this conjecture as a consequence of more general results [25].

There is a much broader literature on permutation classes and pattern-avoiding permutations, including their connections to other well-studied objects in combinatorics and computer science such as stacks, ordered graphs and matrices, and in this short introduction we can only touch upon the tip of the iceberg. We refer the reader to the monographs and surveys of Bona [11], Kitaev [19], Linton [21], Steingrimsson [28] and Vatter [31] for much more on this rich area of combinatorics.

Logical limit laws

A key difference between the study of logical limit laws for random permutations and for random graphs is that unlike in the graph case, there are at least two genuinely different and very natural logics for permutations, each of which has its own advantages. The first logic appeared in [14] and is now known as the Theory of Two Orders (abbreviated as TOTO). This logic concerns a set equipped with two independent linear orders. Informally speaking, one should view permutations in TOTO as a set of points in the plane with no two points placed on the same horizontal or vertical line, and the two orders can be chosen to be the usual orders comparing the x- and y-coordinates of the respective points. TOTO is generally more suitable for problems about pattern-avoidance in permutations, and is the logic we shall consider in this paper; see § 2.1 for a more detailed introduction to TOTO. The second logic, which we will not define here, Theory of One Bijection (TOOB), is more suitable when working with problems that concern the cycle-structure of permutations. For an excellent account of both of these, see e.g. the recent paper of Albert, Bouvel and Féray [6].

For uniform random permutations Foy and Woods [3] showed that in general TOTO formulae do not satisfy a limit law. In 2022 Braunfeld and Kukla [12] showed, among other results, that the class of so-called ‘layered’ permutations satisfies a first-order limit law in TOTO. They also made the rather strong conjecture that every proper permutation class satisfies a first-order limit law in TOTO.

More recently, Albert, Bouvel, Féray and Noy [7] showed that a uniformly chosen random permutation from the class Av(231)\mathrm{Av}(231) of 231231-avoiding permutations satisfies a first-order logical limit law in TOTO. Furthermore, they showed that the set Lim(Av(231))\mathrm{Lim}(\mathrm{Av}(231)) of limits of probabilities that a fixed TOTO sentence is satisfied is dense in [0,1][0,1]. Shortly thereafter, Özdemir [32] obtained a first-order logical limit law in TOTO for Av(321)\mathrm{Av}(321); using symmetries, these results combined imply that all six of the permutation classes Av(σ)\mathrm{Av}(\sigma), σ∈S3\sigma \in \mathfrak{S}_{3}, satisfy a first-order logical limit law.

Recall that very recently the second and third authors proved that any small permutation class is first-order isomorphic to a regular language. This means that there is a bijection from the permutation class to the language, which also extends to a bijection of sentences in first-order logic. Together with further structural properties of this regular language, they concluded that every small permutation class satisfies a first-order convergence law for sentences in TOTO.

Theorem 1.1 (See [25]). Let F\mathcal{F} be a small permutation class.

  1. Then there exists a regular language LFL_{\mathcal{F}} and a length-preserving bijection fF:LF→Ff_{\mathcal{F}}: L_{\mathcal{F}} \rightarrow \mathcal{F} satisfying the following property: for every first-order logic sentence Ψ\Psi on F\mathcal{F} there exists a first-order logic sentence Φ\Phi on LFL_{\mathcal{F}} so that {w∈LF:w⊨Φ}={w∈LF:fF(w)⊨Ψ}.\{w \in L_\mathcal{F}: w \models \Phi\} = \{w \in L_\mathcal{F}: f_\mathcal{F}(w) \models \Psi\}. The same conclusion also holds for sentences in monadic second-order logic.

  2. (sketched) The bijection fFf_\mathcal{F} is in fact a monadic second-order isomorphism: that is, for every sentence Φ\Phi in monadic second-order logic on LFL_\mathcal{F} there exists a corresponding sentence in monadic second-order logic on F\mathcal{F} for which the conclusion above holds. In addition, it is also possible to construct a regular language LF′L_\mathcal{F}' and a length-preserving bijection fF′:LF′→Ff'_\mathcal{F}: L_\mathcal{F}' \rightarrow \mathcal{F} which is a first-order isomorphism.

  3. For the last three assertions, suppose that F\mathcal{F} is not finite. There exist a positive real number α\alpha, a real number β≥1\beta \geq 1, and a non-negative integer cc so that ∣Fn∣=(α+o(1))⋅βn⋅nc.\vert \mathcal{F}_n\vert = (\alpha+o(1))\cdot \beta ^n\cdot n^c.

  4. Given a monadic second-order sentence Ψ\Psi on F\mathcal{F}, write FnΨ:={σ∈Fn:σ⊨Ψ}.\mathcal{F}^\Psi_n := \{\sigma \in \mathcal{F}_n: \sigma \models \Psi\}. Then the sets FnΨ\mathcal{F}^\Psi_n have a rational generating function.

  5. For every first-order TOTO\mathrm{TOTO} sentence Φ\Phi the limit lim⁡n→∞P(π⊨Φ)\lim_{n\rightarrow \infty} \mathbb{P} (\pi \models \Phi) exists, where π\pi is taken uniformly at random from Fn\mathcal{F}_n.

We are now ready to prove the main theorem.

Contributions of this paper

As we have seen, small permutation classes are of interest within the generally challenging theory of permutation classes. They are one of the few significant families of permutation classes for which researchers have been able to derive some general results; in particular small permutation classes have been shown to have a pleasant geometric structure. They are thus a natural first family to study and to try to understand more fully if one is to grapple with permutation classes in their full generality.

For small permutation classes in the polynomial growth regime, we show that the set of limiting probabilities is finite, and determine the set explicitly. As a byproduct of our proof, we also obtain a short alternative proof of the first-order convergence law from [25] for permutation classes of polynomial growth. Before we state our result, let us note that, as a consequence of the work of Kaiser and Klazar [17], if P\mathcal{P} is a small permutation class with polynomial growth then there exist positive integers bb and kk such that ∣Pn∣=b(nk−1)+O(nk−2)\left\vert \mathcal{P}_{n}\right\vert =b{n \choose k-1}+O\left(n^{k-2}\right) (see the discussion after (3.4)).

Theorem 1.2. Let P\mathcal{P} be a permutation class with polynomial growth for which Pn≠∅\mathcal{P}_{n}\neq\emptyset for all n∈Z>0n \in \mathbb{Z}_{>0}. Let bb and kk be positive integers such that ∣Pn∣=b(nk−1)+O(nk−2)\left\vert \mathcal{P}_{n}\right\vert =b{n \choose k-1}+O\left(n^{k-2}\right). Then

  1. for all first-order sentences Ψ\Psi in TOTO, the probability P(σn⊨Ψ)\mathbb{P} \left( \mathbf{\sigma} _n \models \Psi\right) that a random permutation σn\mathbf{\sigma} _n from Pn\mathcal{P}_n satisfies Ψ\Psi tends to a limit as n→∞n \rightarrow \infty with convergence rate O(n−1)O(n^{-1}).

  2. the set of limiting probabilities Lim(P):=\mathrm{Lim}\left(\mathcal{P}\right):= {lim⁡n→∞P(σn⊨Ψ): Ψ first-order TOTO sentence, σn drawn uniformly at random from Pn}\left\{\lim_{n\rightarrow \infty} \mathbb{P}( \mathbf{\sigma} _n \models \Psi): \ \Psi \textrm{ first-order TOTO sentence},\ \mathbf{\sigma} _n \textrm{ drawn uniformly at random from } \mathcal{P} _n\right\} consists of all the fractions {b′b: b′∈[0,b]∩Z}\left\{ \frac{b'}{b}: \ b'\in\left[0,b\right]\cap\mathbb{Z}\right\}, where the integer bb is defined as above. In particular, this set of limiting probabilities is always finite, and P\mathcal{P} satisfies a 00-11 law if and only if b=1b=1.

In the special case where P\mathcal{P} is the geometric grid class of a signed permutation matrix (see § 2.2 for a formal definition of these terms), our methods allow us to construct an infinite TOTO model for the class P\mathcal{P}.

Theorem 1.3. Let P\mathcal{P} be the geometric grid class of a signed permutation matrix. Then there is a permutation P\mathfrak{P} on an infinite set of points that gives an infinite model for the set of TOTO axioms defining P\mathcal{P} and that is asymptotically almost surely TOTO first-order indistinguishable, as n→∞n\rightarrow \infty, from a permutation σn\mathbf{\sigma} _n drawn uniformly at random from Pn\mathcal{P} _n (i.e. for any fixed Ψ\Psi, the probability that σn⊨Ψ\mathbf{\sigma} _n \models \Psi converges to 11 as n→∞n\rightarrow \infty if P⊨Ψ\mathfrak{P}\models \Psi, and to 00 otherwise).

For small permutation classes in the exponential growth regime we show, analogously to the result from [7] for 231231-avoiding permutations, that the set of limiting probabilities is dense in [0,1][0,1]. However, our proof uses very different methods in order to handle the much more general setting we work in.

Theorem 1.4. Let P\mathcal{P} be a small permutation class with exponential growth. Then Lim(P)\mathrm{Lim}(\mathcal{P}) is a dense subset of [0,1][0,1].

Note that in this regime we rely on the convergence result from [25] and our contribution is thus the density of the set Lim(P)\mathrm{Lim}( \mathcal{P} ).

Preliminaries

Permutations and TOTO

References

  1. [1]Rautenberg, W. (2010). A concise introduction to mathematical logic (p. xxii+319). Springer, New York. https://doi.org/10.1007/978-1-4419-1221-3
  2. [2]Kaufmann, M., & Shelah, S. (1985). On random models of finite power and monadic logic. Discrete Mathematics, 54(3), 285–293. https://doi.org/10.1016/0012-365X(85)90112-8
  3. [3]Foy, J., & Woods, A. R. (1990). Probabilities of sentences about two linear orderings. In Feasible Mathematics: A Mathematical Sciences Institute Workshop, Ithaca, New York, June 1989 (pp. 181–193). Birkhäuser Boston. https://doi.org/10.1007/978-1-4612-3466-1_10
  4. [4]Ehrenfeucht, A. (1960). An application of games to the completeness problem for formalized theories. Fund. Math., 49, 129–141. https://doi.org/10.4064/fm-49-2-129-141
  5. [5]Albert, M., Atkinson, M., Bouvel, M., Ruškuc, N., & Vatter, V. (2013). Geometric grid classes of permutations. Transactions of the American Mathematical Society, 365(11), 5859–5881.
  6. [6]Albert, M., Bouvel, M., & Féray, V. (2020). Two first-order logics of permutations. Journal of Combinatorial Theory, Series A, 171, 105158.
  7. [7]Albert, M., Bouvel, M., Féray, V., & Noy, M. (2024). A logical limit law for $231$-avoiding permutations. Discrete Mathematics & Theoretical Computer Science, 26(Special issues).
  8. [8]Albert, M., Ruškuc, N., & Vatter, V. (2015). Inflations of geometric grid classes of permutations. Israel Journal of Mathematics, 205(1), 73–108.
  9. [9]Alon, N., & Friedgut, E. (2000). On the number of permutations avoiding a given pattern. Journal of Combinatorial Theory, Series A, 89(1), 133–140.
  10. [10]Arratia, R. (1999). On the Stanley-Wilf conjecture for the number of permutations avoiding a given pattern. The Electronic Journal of Combinatorics, N1–N1.
  11. [11]Bóna, M. (2008). Combinatorics of permutations. ACM SIGACT News, 39(4), 21–25.
  12. [12]Braunfeld, S., & Kukla, M. (2022). Logical limit laws for layered permutations and related structures. Enum. Combin. Appl., 2(4), PaperNumberS4PP2.
  13. [13]Fagin, R. (1976). Probabilities on finite models. The Journal of Symbolic Logic, 41(1), 50–58.
  14. [14]Foy, J., & Woods, A. R. (1990). Probabilities of sentences about two linear orderings. Feasible Mathematics: A Mathematical Sciences Institute Workshop, Ithaca, New York, June 1989, 181–193.
  15. [15]Glebskii, Y. V., Kogan, D. I., Liogon'kii, M. I., & Talanov, V. A. (1969). Range and degree of realizability of formulas in the restricted predicate calculus. Cybernetics, 5(2), 142–154.
  16. [16]Pantone, J., & Vatter, V. (2020). Growth rates of permutation classes: Categorization up to the uncountability threshold. Israel Journal of Mathematics, 236, 1–43.
  17. [17]Kaiser, T., & Klazar, M. (2002). On growth rates of closed permutation classes. The Electronic Journal of Combinatorics, R10–R10.
  18. [18]Albert, M., Atkinson, M., & Brignall, R. (2007). Permutation Classes of Polynomial Growth. Annals of Combinatorics, 11, 249–264.
  19. [19]Kitaev, S. (2010). A survey on partially ordered patterns. Permutation Patterns, 376, 115–135.
  20. [20]Huczynska, S., & Vatter, V. (2006). Grid classes and the Fibonacci dichotomy for restricted permutations.. The Electronic Journal of Combinatorics, 13, PaperR54.
  21. [21]Linton, S., Ruškuc, N., & Vatter, V. (2010). Permutation patterns (Vol. 376). Cambridge University Press.
  22. [22]Klazar, M. (2000). The Füredi--Hajnal conjecture implies the Stanley--Wilf conjecture. Formal Power Series and Algebraic Combinatorics: 12th International Conference, FPSAC’00, Moscow, Russia, June 2000, Proceedings, 250–255.
  23. [23]Knuth, D. E. (1968). The Art of Computer Programming, Volume 1. Addison-Wesley Professional.
  24. [24]Marcus, A., & Tardos, G. (2004). Excluded permutation matrices and the Stanley--Wilf conjecture. Journal of Combinatorial Theory, Series A, 107(1), 153–160.
  25. [25]Markström, K., & Räty, E. (2025). Logical isomorphism and logical limit laws for small permutation classes and regular languages. https://arxiv.org/abs/2610.22218
  26. [26]Müller, T., Skerman, F., & Verstraaten, T. W. (2025). Logical Limit Laws for Mallows Random Permutations. Electron. J. Combin., 32(4), P4.67. https://doi.org/10.37236/13047
  27. [27]Spencer, J. (2013). The strange logic of random graphs (Vol. 22). Springer Science & Business Media.
  28. [28]Steingrímsson, E. (2013). Some open problems on permutation patterns.. Surveys in Combinatorics, 409, 239–263.
  29. [29]Vatter, V. (2011). Small permutation classes. Proceedings of the London Mathematical Society, 103(5), 879–921.
  30. [30]Vatter, V. (2010). Permutation classes of every growth rate above 2.48188. Mathematika, 56(1), 182–192.
  31. [31]Vatter, V. (2015). Permutation classes. Handbook of Enumerative Combinatorics, 754–833.
  32. [32]Özdemir, A. (2026). First-order convergence for $321 $-avoiding permutations. Discrete Mathematics, 349(8), 115149.

Paper details

vlnc:W_6dzabad9
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 8

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

GPT-4, GPT-6 Astra

View statement
Looking for related papers…
Contents