Asymptotic Behaviour of the Containment of Certain Mesh Patterns

NEW

Problem: The intended Conjecture 5.1 is the following. Let $p=(2143,R)$ be the mesh pattern with

$$R=\{(0,0),(1,0),(2,0),(3,0),(4,1),(4,2),(4,3),(0,4),(1,4),(2,4),(3,4),(4,4)\}.$$

Let $s_n^+(p)$ be the number of permutations in $S_n$ containing $p$ in the usual mesh-pattern sense. Then

$$\lim_{n\to\infty}\frac{s_n^+(p)}{n!}=\frac12 .$$

The input lost the displayed pattern; the source TeX gives exactly this $\patt{}{4}{2,1,4,3}$-pattern.

Result: Let

$$p^+=(2143,R\cup\{(4,0)\}).$$

Since $R\subset R\cup\{(4,0)\}$, every occurrence of $p^+$ is an occurrence of $p$.

First, $\Pr(\sigma\in S_n\text{ contains }p^+)\to 1/2$. For $p^+$, the shading forces an occurrence to be a subword

$$a\,1\,n\,\sigma_n$$

with $1<a<\sigma_n<n$. Thus containment implies that $1$ occurs before $n$, an event of probability $1/2$. Conversely, if $1$ occurs before $n$, $n$ is not last, and some entry before $1$ lies in $\{2,\dots,\sigma_n-1\}$, then $p^+$ occurs.

Conditioning on $\sigma_n=j$, the probability that no element of $\{2,\dots,j-1\}$ occurs before $1$ is $1/(j-1)$. Hence the exceptional probability is at most

$$\frac1n+\frac1n\sum_{j=2}^n \frac1{j-1}=O\!\left(\frac{\log n}{n}\right).$$

Therefore

$$\Pr(\sigma\text{ contains }p^+)\to \frac12 .$$

It remains to show that $p$-containment without $p^+$-containment is negligible. Suppose $p$ occurs in $\sigma$ at positions

$$i_1<i_2<i_3<i_4$$

with selected values $v_1,v_2,v_3,v_4$, so

$$v_2<v_1<v_4<v_3.$$

The top-row shading forces $v_3=n$. The bottom-row shading except $(4,0)$ forces all values $<v_2$ to lie after $i_4$. The right-column shading forces every value after $i_4$ to be $<v_2$. Hence the suffix after $i_4$ is exactly

$$\{1,\dots,v_2-1\},$$

so the prefix of length $m=i_4$ is exactly the set of largest $m$ values. If $m=n$, the same occurrence also satisfies the extra shaded cell $(4,0)$, so it is an occurrence of $p^+$. Thus a permutation containing $p$ but not $p^+$ has a proper skew cut: for some $1\le m<n$, its first $m$ entries are precisely the largest $m$ values.

For fixed $m$, this has probability $\binom{n}{m}^{-1}$. Therefore

$$\Pr(p\text{ occurs but }p^+\text{ does not}) \le \sum_{m=1}^{n-1}\binom{n}{m}^{-1} \le \frac{4}{n}=o(1).$$

Thus

$$\Pr(p^+\text{ occurs}) \le \Pr(p\text{ occurs}) \le \Pr(p^+\text{ occurs})+o(1),$$

and so

$$\lim_{n\to\infty}\frac{s_n^+(p)}{n!}=\frac12 .$$

Citation: Govc and Smith, “Asymptotic Behaviour of the Containment of Certain Mesh Patterns,” arXiv:2011.11382, Section 5, Conjecture 5.1. The proof above resolves that conjecture; the auxiliary $p^+$ case is their side-shaded pattern.