Sign Up

Ewing Hall, University of Delaware, Newark, DE 19716, USA

View map

A \it cluster\rm\ of length $l$ in a permutation from $S_n$ is a set of $l$ consecutive numbers that appear in any order in $l$ consecutive positions in the permutation. For $n\ge l\ge2$ and $\tau\in S_l$, let $ N^{(n)}_{l}(\sigma)$ denote  the number of clusters of length $l$ in $\sigma$, and let $ N^{(n)}_{l;\tau}(\sigma)$ denote the number of clusters of length $l$ whose order is the pattern $\tau$. (For example, $\sigma=317564928\in S_9$ has the cluster 7564 of length $l=4$ and pattern $\tau=4231$.)

 

For $\eta\in S_3$,  let $S_n^{\text{av}(\eta)}$ denote the set of  permutations in $S_n$ that avoid the pattern $\eta$, and let $E_n^{\text{av}(\eta)}$ denote the expectation
with respect to the uniform probability measure on $S_n^{\text{av}(\eta)}$. We obtain explicit formulas for $E_n^{\text{av}(\eta)} N^{(n)}_{l;\tau}$ and $E_n^{\text{av}(\eta)}N^{(n)}_{l}$. These exact formulas yield  asymptotic formulas as $n\to\infty$ with $l$ fixed,  and also with   $l=l_n\to\infty$.

 

In particular, for fixed $l$, depending on $\eta$ and $\tau$,  the  expectation $E_n^{\text{av}(\eta)} N^{(n)}_{l;\tau}$ either  grows linearly in $n$ or is bounded and bounded away from zero. The expectation $E_n^{\text{av}(\eta)}N^{(n)}_{l}$ always has linear growth in $n$, when $l$ is fixed. For   certain $\eta\in S_3$,   $\lim_{n\to\infty}E_n^{\text{av}(\eta)}N^{(n)}_{l_n}$ is equal to infinity or zero depending on whether $l_n$ is on an order less than $n^\frac23$ or greater than $n^\frac23$, while for other $\eta\in S_3$, this dichotomy occurs depending on whether $\lim_{n\to\infty}(l_n-\frac{\log n}{\log 4})$ is equal to $-\infty$ or $+\infty$.

 

Analogous results are obtained for $S_n^{\text{av}(\eta_1,\cdots,\eta_r)}$, the  permutations in $S_n$ simultaneously avoiding the patterns $\{\eta_i\}_{i=1}^r$, in the case that $\{\eta_i\}_{i=1}^n$ are all \it simple\rm\ permutations. A particular case of this, where we can calculate the asymptotic behavior explicitly,  is the set of \it separable\rm\ permutations, which corresponds to $r=2$, $\eta_1=2413,\eta_2=3142$.

Event Details

See Who Is Interested

0 people are interested in this event

User Activity

No recent activity