pith. sign in

arxiv: 2604.23751 · v1 · submitted 2026-04-26 · 🧮 math.PR · math.CO

Large deviation principles for pattern-avoiding permutations, and limit shapes for constrained Mallows permutations

Thomas Budzinski , Victor Dubach , Valentin F\'eray , Mohamed Slim Kammoun , Myl\`ene Ma\"ida This is my paper

Pith reviewed 2026-05-08 05:35 UTC · model grok-4.3

classification 🧮 math.PR math.CO
keywords pattern-avoiding permutationsMallows permutationspermutonslarge deviation principlesq-Catalan numberslimit shapesconstrained random permutationsbeta-biased models
0
0 comments X

The pith

Mallows permutations conditioned to avoid a length-3 pattern converge to an explicit deterministic permuton when the bias scales as e to the beta over n.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper studies Mallows random permutations that must avoid one fixed pattern of length three. For bias parameters of the precise form e to the power beta over n, the conditioned permutations converge in law to a deterministic permuton whose shape is written down explicitly from the avoided pattern and the value of beta. A sympathetic reader cares because this gives a concrete geometric picture of how the bias and the avoidance constraint together shape the typical ordering. The proof proceeds by first parametrizing all possible permutons that avoid the pattern, then establishing a large deviation principle that governs the uniform measure on those avoiding permutations, and finally locating the unique minimizer of the resulting rate function after the Mallows tilt. As a byproduct the same argument supplies asymptotic growth rates for two families of q-Catalan numbers in the regime where q equals e to the beta over n.

Core claim

When the Mallows measure is restricted to permutations avoiding a fixed length-three pattern alpha and the bias parameter is set to e to the beta over n, the random permutation converges in the permuton topology to a deterministic limit whose density is an explicit function of alpha and beta. The limit is obtained by combining a parametrization of the entire set of alpha-avoiding permutons with a large-deviation principle for the uniform law on that set; the Mallows tilt then selects a unique minimizer of the rate function, which turns out to be non-degenerate for every real beta.

What carries the argument

Parametrizations of the space of alpha-avoiding permutons together with the large-deviation rate function for the uniform measure on that space; the Mallows exponential tilt selects the explicit minimizer.

If this is right

  • The limiting permuton is non-trivial and depends on both the specific avoided pattern and the numerical value of beta.
  • Uniform alpha-avoiding permutations obey a large-deviation principle whose rate function is explicit once the parametrization is fixed.
  • Two versions of the q-Catalan numbers admit precise asymptotic formulas when q equals e to the beta over n.
  • The same minimizer construction yields a concrete description of the most likely alpha-avoiding permuton under the tilted measure.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The explicit form of the limiting permuton makes it possible to read off limiting values of many other statistics, such as the expected number of a second pattern or the distribution of inversion tables.
  • If analogous parametrizations can be found for longer avoided patterns, the same large-deviation-plus-tilt strategy would produce limit shapes in those cases as well.
  • The q-Catalan asymptotics obtained here sit at the boundary between combinatorial enumeration and probabilistic limit theorems and may be useful for analyzing other q-analogues of Catalan structures.

Load-bearing premise

The bias must be exactly of order one over n and the forbidden pattern must have length exactly three so that the parametrizations and the large-deviation principle can be used to locate an explicit minimizer.

What would settle it

Generate many independent samples of length-n Mallows permutations conditioned on avoiding a fixed length-three pattern with bias e to the beta over n, form their empirical permutons, and check whether the L1 distance to the predicted explicit density tends to zero as n tends to infinity.

Figures

Figures reproduced from arXiv: 2604.23751 by Mohamed Slim Kammoun, Myl\`ene Ma\"ida, Thomas Budzinski, Valentin F\'eray, Victor Dubach.

Figure 1
Figure 1. Figure 1: Top line: simulations of 321-avoiding Mallows permutations with size 600 and bias parameter q = e β/n, for β ∈ {1, 3, 12}. Bottom line: likewise with 231-avoiding Mallows permutations. Here, and throughout the paper, a permutation σ is represented graphically by the set {(i, σ(i)), 1 ≤ i ≤ n}. 2020 Mathematics Subject Classification. 05A05, 05A19, 60C05, 60F10. Key words and phrases. Random permutations, p… view at source ↗
Figure 2
Figure 2. Figure 2: Illustration of the parametrizations of 231- and 321-avoiding per￾mutons. 321-avoiding permutons are in bijection with excursions, obtained by rotating and flipping their RLM curves (in red on the figure). On the other hand, there is a continuous surjection from pairs of measures to 231-avoiding permutons (the measures π1 and π2 are here represented by the graphs of their densities); informally, these meas… view at source ↗
Figure 3
Figure 3. Figure 3: Black dots: simulations of τ β,α n with n = 600 and β ∈ {1, 3, 6, 12}. Red curves: support of the limit permutons µ α β , again for β ∈ {1, 3, 6, 12}. Left: α = 321. Right: α = 231. In particular, we see that µ 231 β is supported on the union of an increasing curve and a part of the decreasing diagonal, namely {(x, 1 − x) : 0 ≤ x ≤ x ∗ β }, where x ∗ β fulfills (f 231 β ) ′ (x ∗ β ) = 1 (explicitly, x ∗ β … view at source ↗
Figure 4
Figure 4. Figure 4: Our second family of examples illustrates the opposite situation. Here, we choose two sets of right-to-left minima such that the associated RLM curves are close to each other, but the associated pairs of measures are very different (because one contains twice as many RLMs as the other). In this case, the corresponding 231-avoiding permutations converge to the same permuton, but not the corresponding 321-av… view at source ↗
Figure 4
Figure 4. Figure 4: Examples of α-avoiding permutations of size 120 with given right-to￾left minima on the left, and their limit permutons on the right. In red, we plot the RLM curves of the permutations/permutons (slightly shifted so that they do not hide the points). In the top line α = 321, while in the bottom line α = 231. First column: RLMs are the points (2i, i) for i < 1 4 n, ( 1 2 n, 1 2 n), and (n−i, n−2i) for i < 1 … view at source ↗
Figure 5
Figure 5. Figure 5: Further examples of α-avoiding permutations of size 120 with given right-to-left minima on the left, and their limit permutons on the right. In the top line α = 321, while in the bottom line α = 231. First column: RLMs are the points ( 1 2 n + i, i) for i ≤ 1 2 n. Second column: we keep only half of the RLMs, namely the RLMs are the points ( 1 2 n + 2i, 2i) for i ≤ 1 4 n. 10 view at source ↗
Figure 6
Figure 6. Figure 6: Left: a 321-avoiding permutation σ, with its strict RL minima in red. The corresponding list encoding is ((2, 1),(4, 2),(7, 6),(8, 7)). Note that the element (5, 5) is a weak RL minimum (in the sense that it is a fixed point of the permutation) and does not appear in the list. Right: the support of a 321- avoiding permuton µ = Ψ(π1, π2). The support of π1 ↗ π2 is in red. A point (x, y) on the red curve sho… view at source ↗
Figure 7
Figure 7. Figure 7: Left: a 231-avoiding permutation σ of size 15. Its set of RL minima, and the associated curve Fσ, are shown in red. Right: the Dyck path Φσ of length 30 obtained by rotating and flipping the RLM curve. Substituting g := e β(f−1/2), we find that g ′ = qg(1 + g) where q(x) := β 1+e β(1/2−x) . This is a simple Riccati equation, which can be solved7 by g(x) = − e βx + e β/2 e βx + c for c ∈ R (the only other s… view at source ↗
Figure 8
Figure 8. Figure 8: Illustration of (25). Left: the point (x ′ , y′ ) is one of the closest to the diagonal of [0, 1]2 in Gf (x, y). Right: It can actually be shown that the permuton with RLM-curve f has support contained in the shaded area (see the proof of Lemma 26), explaining the formula (25). Lemma 25. Let f ∈ F. There exists a unique 231-avoiding permuton µf such that (26) for all (x, y) ∈ [0, 1]2 , µf ([x, 1] × [0, y])… view at source ↗
Figure 9
Figure 9. Figure 9: Illustration of the proof of Lemma 25. Left: we consider two hypo￾thetical points (x1, y1) and (x2, y2) with y1 < y2 and x1 < x2 < f −1 (y1). The minimum of x ′−y ′ on the curve Gf below and on the right of p1 := (x1+ε, y1+ε) is reached somewhere in the horizontal light gray band, namely in m1. On the other hand, the minimum of x ′ − y ′ on the curve Gf below and on the right of p2 := (x2 − ε, y2 − ε) is r… view at source ↗
Figure 10
Figure 10. Figure 10: Illustration of the proof of Lemma 26. The black curve is the graph Gf of f, and gray fat squares represent excursions of f. The black disks with some gray zones around are points of the support of ν with some zone having a positive mass around them. The crosses are points that are not necessarily in the support. Left: we assume by contradiction that there is some mass below a point (x1, y1) on the left o… view at source ↗
Figure 11
Figure 11. Figure 11: Construction of the sequence (yn) in the proof of Lemma 28, (iii) =⇒ (i). well. Now let ε > 0. For large enough n, the graph Gφ is contained within the ε-halo of Gφn . Consequently, for any x in [0, 1], there exists xn ∈ [0, 1] such that |xn − x| < ε and |φn(xn) − φ(x)| < ε. Since φn is 1-Lipschitz, we deduce that |φn(x) − φ(x)| < 2ε. This proves that φn → φ uniformly. (iii) =⇒ (i). Assume that φn → φ uni… view at source ↗
read the original abstract

We study Mallows random permutations conditioned to avoid a given pattern $\alpha$ of length~$3$. When the bias parameter is of the form $e^{\beta/n}$, we prove that these permutations converge to a non-trivial explicit deterministic permuton that depends on the pattern $\alpha$ and on the parameter $\beta$. Along the way, we provide parametrizations for $\alpha$-avoiding permutons, and establish a large deviation principle for uniform $\alpha$-avoiding permutations. As a byproduct of the proof, we also obtain asymptotic estimates of two versions of $q$-Catalan numbers in the regime $q=e^{\beta/n}$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript studies Mallows random permutations conditioned to avoid a fixed length-3 pattern α. For bias parameter q = e^{β/n}, it proves convergence in the permuton topology to a non-trivial explicit deterministic limit permuton depending on α and β. Along the way it supplies explicit parametrizations of α-avoiding permutons (via integral representations and q-analogues of Dyck paths), establishes a large deviation principle for the uniform measure on α-avoiding permutations in the space of permutons equipped with the Lévy-Prokhorov metric, and derives asymptotic estimates for two versions of q-Catalan numbers in the same regime.

Significance. If the derivations hold, the work supplies concrete, explicit limit shapes for a natural class of constrained biased permutations and equips the field with usable parametrizations and an LDP that can be applied to other pattern-avoiding models. The identification of the limit as the unique minimizer of the rate function plus β times the inversion density is a clean application of the LDP, and the q-Catalan asymptotics constitute a useful combinatorial byproduct.

major comments (2)
  1. [LDP section] The section establishing the LDP: the proof that the rate function is lower semi-continuous with compact level sets in the Lévy-Prokhorov topology on permutons is load-bearing for the subsequent concentration argument; the manuscript must confirm that the inversion functional is continuous on this space so that the tilted functional attains its minimum at a unique point.
  2. [Parametrization of α-avoiding permutons] The parametrization section: the claim that the supplied integral representations (or generating-function descriptions tied to Dyck paths) exhaust all α-avoiding permutons for α = 132, 213, 231, 312 is essential for guaranteeing that the minimizer of the rate-plus-inversion functional lies inside the parametrized set and is therefore explicit and deterministic.
minor comments (2)
  1. [Abstract] The abstract states that two versions of q-Catalan numbers are treated; a brief parenthetical identifying the two versions (e.g., the standard and the inversion-weighted versions) would improve immediate readability.
  2. [Main argument] Notation: the precise definition of the inversion density functional on the space of permutons should be recalled or cross-referenced when it is first used in the tilting argument, to aid readers who may not have the preceding literature at hand.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their positive evaluation of our manuscript and for the constructive major comments. We address each point below, clarifying the relevant sections and indicating where minor additions will be made in the revised version.

read point-by-point responses

  1. Referee: [LDP section] The section establishing the LDP: the proof that the rate function is lower semi-continuous with compact level sets in the Lévy-Prokhorov topology on permutons is load-bearing for the subsequent concentration argument; the manuscript must confirm that the inversion functional is continuous on this space so that the tilted functional attains its minimum at a unique point.

    Authors: We agree that explicit confirmation of the continuity of the inversion functional is important for the argument. In Section 3, the LDP is established for the uniform measure on α-avoiding permutations under the Lévy-Prokhorov metric on permutons. The rate function is shown to be lower semi-continuous with compact level sets by standard arguments in the space of permutons. The inversion density is continuous in this topology because it equals the double integral of the indicator 1_{x>y} against the permuton measure μ, and weak convergence of measures in the Lévy-Prokhorov metric preserves such integrals for bounded continuous test functions. Consequently the tilted functional (rate plus β times inversion density) is lower semi-continuous and, by strict convexity of the rate function on the convex set of α-avoiding permutons, attains its minimum at a unique point. We will insert a short paragraph in the revised manuscript explicitly recording this continuity statement and its consequence for uniqueness. revision: partial

  2. Referee: [Parametrization of α-avoiding permutons] The parametrization section: the claim that the supplied integral representations (or generating-function descriptions tied to Dyck paths) exhaust all α-avoiding permutons for α = 132, 213, 231, 312 is essential for guaranteeing that the minimizer of the rate-plus-inversion functional lies inside the parametrized set and is therefore explicit and deterministic.

    Authors: The parametrizations in Section 2 are constructed precisely to be exhaustive. For each α in {132,213,231,312} we start from the classical bijection between α-avoiding permutations and Dyck paths (or lattice paths) and pass to the permuton limit; the resulting integral representations (or the q-analogues of the generating functions) are shown to describe every possible weak limit of α-avoiding permutation matrices. The proof proceeds by verifying that any α-avoiding permuton admits a disintegration along the corresponding path measure, which is always representable in the stated integral form. Because the unique minimizer of the tilted rate function lies in the closed convex set of α-avoiding permutons, it necessarily belongs to the parametrized family and is therefore explicit. This exhaustiveness is already proved in the manuscript; no further revision is required. revision: no

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The manuscript proves its own large deviation principle for the uniform measure on α-avoiding permutations (in the space of permutons) and supplies explicit parametrizations of the admissible permutons (via integral representations or generating functions linked to Dyck paths). These ingredients are then applied to the exponentially tilted Mallows measure (q = e^{β/n}) by minimizing the sum of the rate function and β times the inversion density. The resulting concentration on a unique explicit minimizer is a direct, non-circular consequence of the LDP and continuity of the inversion functional; no step reduces by construction to a fitted parameter, self-citation, or ansatz imported from the authors' prior work.

Axiom & Free-Parameter Ledger

1 free parameters · 2 axioms · 0 invented entities

The central claims rest on standard tools from large deviations and permuton theory applied to the Mallows conditioning; the specific application and explicit forms constitute the addition beyond prior work. No new entities are postulated.

free parameters (1)
  • β
    The continuous parameter controlling the strength of the Mallows bias in the scaled regime; the limit shape depends on its value.
axioms (2)
  • domain assumption Large deviation principle holds for the uniform measure on α-avoiding permutations
    Invoked to obtain the conditioned limit under the Mallows measure with small bias.
  • domain assumption α-avoiding permutons admit explicit parametrizations
    Used to identify the deterministic limit shape for each pattern α.

pith-pipeline@v0.9.0 · 5422 in / 1457 out tokens · 75702 ms · 2026-05-08T05:35:27.936839+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

5 extracted references · 5 canonical work pages

  1. [1]

    Borga, S

    [BDMW24] J. Borga, S. Das, S. Mukherjee, and P. Winkler. Large deviation principle for random permutations. Int. Math. Res. Not., 2024(3):2138–2191,

    work page 2024

  2. [2]

    [CEKS13] S.-E

    Preprint arXiv:0711.2684. [CEKS13] S.-E. Cheng, S. Elizalde, A. Kasraoui, and B. E. Sagan. Inversion polynomials for 321-avoiding permutations.Discrete Math., 313(22):2552–2565,

    work page arXiv

  3. [3]

    Madras and H

    [ML10] N. Madras and H. Liu. Random pattern-avoiding permutations. InAlgorithmic probability and com- binatorics. Papers from the AMS special sessions, Chicago, IL, USA, October 5–6, 2007 and Van- couver, BC, Canada, October 4–5, 2008, pages 173–194. Providence, RI: American Mathematical Society (AMS),

    work page 2007

  4. [4]

    McShine and P

    [MT99] L. McShine and P. Tetali. On the mixing time of the triangulation walk and other Catalan structures. InRandomization methods in algorithm design. DIMACS workshop, Princeton Univ., NJ, USA, December 12–14, 1997, pages 147–160. Providence, RI: AMS, American Mathematical Society,

    work page 1997

  5. [5]

    [Sta09] S

    preprint arXiv:2512.25006. [Sta09] S. Starr. Thermodynamic limit for the Mallows model onS n.J. Math. Phys., 50(9):nb. 095208, 15 pp.,

    work page arXiv