Random periodic pattern-avoiding permutations
As a fresh way to think about the probabilistic structure of pattern- avoiding permutations, we examine affine permutations with a new ”boundedness” condition. We view this as an analogue of the useful concept of periodic boundary conditions in statistical physics. An affine permutation of period N is a bijection ω of Z satisfying
ω(i + N) = ω(i) + N for every i ∈ Z
as well as the centering condition
ω(i) = i, i=1 i=1
and we say it is bounded if
|ω(i) − i| < N for every i ∈ Z.
Let BAN be the set of bounded affine permutations of period N. Note that for any (ordinary) permutation σ on {1, . . . , N }, the periodic extension of σ viaσ(i+kN)=σ(i)+kN (k∈Z)isinBAN.
For a fixed short permutation τ, let AvBAN(τ) be the set of ω ∈ BAN that avoid the pattern τ (i.e., viewing a permutation as a sequence of in- tegers, ω has no subsequence with the same relative order as τ). We fo- cus on the decreasing pattern Decrk := k(k−1) · · · 321 for fixed k ≥ 3. We explain how a probabilistic viewpoint enables us to obtain the cardi- nality of AvBAN(Decrk) asymptotically as N → ∞, and as a bonus to derive a permuton-like scaling limit for the plot of a random element of AvBAN(Decrk) as N → ∞.
This is joint work with Justin Troyka. The research was supported in part by an NSERC Discovery Grant and by York University’s Faculty of Science.