# Shape Avoiding Permutations

## 1 Introduction

### 1.1 Outline

The Robinson-Schensted(-Knuth) correspondence is a bijection between permutations in $`S_n`$ and pairs of standard Young tableaux of the same shape (and size $`n`$). This common shape is called the shape of the permutation. A permutation $`\pi =(\pi _1,\mathrm{},\pi _n)`$ in $`S_n`$ avoids a permutation $`\sigma =(\sigma _1,\mathrm{},\sigma _m)`$ in $`S_m`$ if there is no subsequence $`(\pi _{i_1},\mathrm{},\pi _{i_m})`$ of $`\pi `$ such that $`\pi _{i_j}>\pi _{i_k}`$ iff $`\sigma _j>\sigma _k`$ ($`j,k`$). $`\pi `$ avoids a shape $`\mu `$ if it avoids all the permutations of shape $`\mu `$.

This paper deals with the relation between the property “$`\pi `$ does not avoid a given shape $`\mu `$” and the property “$`\lambda =\mathrm{𝑠ℎ𝑎𝑝𝑒}(\pi )`$ contains $`\mu `$ as a sub-shape”. It turns out that, in general, neither of these properties implies or contradicts the other; but in certain important cases, such implications do hold. These cases include, e.g., rectangular shapes and hook shapes (either for $`\lambda `$ or for $`\mu `$). These positive results are then applied to get asymptotic bounds related to the Stanley-Wilf conjecture on pattern-avoiding permutations (see Corollaries 4 and 5 in Subsection 1.2, and Subsection 7.2). Use is made of the Berele-Regev asymptotic evaluation of the number of standard Young tableaux contained in a “thick hook”.

The rest of the paper is organized as follows. The main results are listed in Subsection 1.2. Standard notations and necessary background are given in Section 2. In Section 3 we motivate our investigation by a “false conjecture”. In Section 4 we show that this “false conjecture” is correct for rectangular shapes. Using this knowledge we consider the general case in Section 5. Families of shapes, for which an exact evaluation may be obtained, are presented in Section 6. Section 7 concludes the paper with final remarks and open problems.

### 1.2 Main Results

For rectangular shapes the following holds.

Theorem 1. If $`\pi `$ is a permutation of rectangular shape $`(m^k)`$, and $`\mu `$ is an arbitrary shape, then:

$`\mu `$ is the shape of some subsequence of $`\pi `$ if and only if $`\mu (m^k)`$.

See Theorem 4.1 below.

Using Theorem 1 we prove the following general result.

Theorem 2. For any permutation $`\pi `$ in $`S_n`$ and any partition $`\mu =(\mu _1,\mathrm{},\mu _k)`$ of $`m`$ :

If $`(\mu _1^k)\mathrm{𝑠ℎ𝑎𝑝𝑒}(\pi )`$ then $`\mu `$ is the shape of some subsequence of $`\pi `$.

See Theorem 5.1 below.

For hook shapes a stronger result is proved.

Theorem 3. Let $`m`$ and $`k`$ be positive integers and let $`n4km`$. Then for any hook $`\mu =(m,1^{k1})`$ and any permutation $`\pi `$ in $`S_n`$ :

$`\pi `$ has a subsequence of shape $`\mu `$ if and only if $`\mu \mathrm{𝑠ℎ𝑎𝑝𝑒}(\pi )`$.

See Theorem 6.1 below.

Denote by $`\mathrm{𝑎𝑣𝑜𝑖𝑑}_n^\mu `$ the size of the set of all $`\mu `$-avoiding permutations in $`S_n`$. Combining Theorem 2 with the Berele-Regev asymptotic estimates \[BR\] the following bounds are proved.

Corollary 4. For any fixed partition $`\mu =(\mu _1,\mathrm{},\mu _k)`$,

$$\mathrm{max}\{\text{ht}(\mu ),\text{wd}(\mu )\}\underset{n\mathrm{}}{lim\; inf}(\mathrm{𝑎𝑣𝑜𝑖𝑑}_n^\mu )^{1/2n}$$

and

$$\underset{n\mathrm{}}{lim\; sup}(\mathrm{𝑎𝑣𝑜𝑖𝑑}_n^\mu )^{1/2n}\text{ht}(\mu )+\text{wd}(\mu ),$$

where the height of $`\mu `$ $`\text{ht}(\mu ):=k1`$, and the width of $`\mu `$ $`\text{wd}(\mu ):=\mu _11`$.

See Corollary 5.2 below. It should be noted that this result is related to the Stanley-Wilf conjecture (see Subsection 7.2).

For hook shapes we have a sharper estimate.

Corollary 5. For any pair of positive integers $`m`$ and $`k`$

$$\underset{n\mathrm{}}{lim}(\mathrm{𝑎𝑣𝑜𝑖𝑑}_n^{(m,1^{k1})})^{1/2n}=\mathrm{max}\{m1,k1\}.$$

See Corollary 6.5 below.

## 2 Preliminaries

Two classical partial orders on the set of partitions are considered in this paper. Let $`\lambda =(\lambda _1,\mathrm{})`$ and $`\mu =(\mu _1,\mathrm{})`$ be two partitions (not necessarily of the same number).

We say that $`\mu `$ is contained in $`\lambda `$, denoted $`\mu \lambda `$, if

$$\mu _i\lambda _i(i).$$

We say that $`\mu `$ is dominated by $`\lambda `$, denoted $`\mu \lambda `$, if

$$\underset{j=1}{\overset{i}{}}\mu _j\underset{j=1}{\overset{i}{}}\lambda _j(i).$$

Clearly, $`\mu \lambda \mu \lambda `$.

The partition conjugate to $`\lambda `$ is $`\lambda ^{}=(\lambda _1^{},\mathrm{})`$, where $`\lambda _i^{}=\mathrm{max}\{j|\lambda _ji\}`$; i.e., the conjugate partition is obtained by interchanging rows and columns in $`\lambda `$.

Lemma 2.1. \[Md Ch. I (1.11)\] If $`\lambda `$ and $`\mu `$ are partitions of the same number $`n`$ then

$$\mu \lambda \lambda ^{}\mu ^{}.$$

Corollary 2.2. If $`\lambda `$ and $`\mu `$ are partitions of the same number $`n`$, satisfying

$$\mu \lambda \text{ and }\mu ^{}\lambda ^{}$$

then $`\lambda =\mu `$.

Define the shape of a sequence of integers to be the common shape of the two tableaux obtained via the Robinson-Schensted-Knuth correspondence. See \[Sa §3.3, St §7.11\]. The following theorem is well known.

Schensted’s Theorem. \[Sc\] For any partition $`\lambda `$ and any permutation $`\pi `$ of shape $`\lambda `$, the length of the longest increasing subsequence of $`\pi `$ is equal to $`\lambda _1`$, and the length of the longest decreasing subsequence of $`\pi `$ is equal to $`\lambda _1^{}`$.

Schensted’s Theorem was generalized by Greene.

Greene’s Theorem. \[Gr\] Let $`\pi `$ be a permutation of shape $`\lambda =(\lambda _1,\mathrm{},\lambda _t)`$. Then, for all $`i`$:

$$\underset{j=1}{\overset{i}{}}\lambda _j=\text{ maximal size of a union of }i\text{ increasing subsequences in }\pi ,$$

and

$$\underset{j=1}{\overset{i}{}}\lambda _j^{}=\text{ maximal size of a union of }i\text{ decreasing subsequences in }\pi .$$

## 3 Motivation

Let $`\mu `$ be a partition of $`m`$, and let $`C^\mu `$ be the set of all permutations in $`S_m`$ of shape $`\mu `$. A permutation in $`S_n`$ is a $`\mu `$-avoiding permutation if it avoids all the permutations in $`C^\mu `$; denote the set of these permutations by $`\mathrm{𝐴𝑣𝑜𝑖𝑑}_n^\mu `$.

The only permutation in $`S_m`$ having shape $`(m)`$ is the identity permutation, i.e., a monotone increasing sequence. Schensted’s Theorem, stated in the previous section, is thus equivalent to the following statement.

Fact 3.1. For any pair of positive integers $`mn`$

$$\mathrm{𝐴𝑣𝑜𝑖𝑑}_n^{(m)}=\underset{\{\lambda n|(m)\lambda \}}{}C^\lambda ,$$

and similarly for $`(1^m)`$ instead of $`(m)`$.

In other words, the set of permutations in $`S_n`$ avoiding $`(m)`$ is the union of all Knuth cells of shapes not containing $`(m)`$. One may be tempted to think that this is a general phenomenon.

“False Conjecture” (First Version). For any pair of positive integers $`mn`$ and any partition $`\mu `$ of $`m`$

$$\mathrm{𝐴𝑣𝑜𝑖𝑑}_n^\mu =\underset{\{\lambda n|\mu \lambda \}}{}C^\lambda .$$

Equivalently,

“False Conjecture” (Second Version). For any permutation $`\pi S_n`$ of shape $`\lambda `$, the following two assertions hold:

* For any partition $`\mu \lambda `$ there exists a subsequence of $`\pi `$ of shape $`\mu `$.
* The shape of any subsequence of $`\pi `$ is contained in $`\lambda `$.

Clearly, (1) is equivalent to the inclusion

$$\mathrm{𝐴𝑣𝑜𝑖𝑑}_n^\mu \underset{\{\lambda n|\mu \lambda \}}{}C^\lambda ,$$

while (2) is equivalent to the reverse inclusion

$$\underset{\{\lambda n|\mu \lambda \}}{}C^\lambda \mathrm{𝐴𝑣𝑜𝑖𝑑}_n^\mu .$$

Note that Greene’s Theorem implies the weaker result that the shape of any subsequence of $`\pi `$ is dominated by $`\lambda `$.

Unfortunately, the following examples show that both parts of the “False Conjecture” are false in general.

Example 3.2. The permutation $`\pi =(65127843)`$ has shape $`\lambda =(4,2,1^2)`$, but has no subsequence of shape $`\mu =(4,1^3)`$.

Example 3.3. The permutation $`\pi =(25314)`$ has shape $`\lambda =(3,1^2)`$, but has a subsequence of shape $`\mu =(2^2)`$.

Both examples can be extended to shapes $`\lambda `$ of arbitrarily large size.

A central discovery in this paper is that the above “False Conjecture” is nevertheless correct in some important cases. This will be used to deduce asymptotic estimates.

## 4 Rectangular Shapes

A rectangular shape is a shape of the form $`(m^k)`$, where $`m`$ and $`k`$ are positive integers. In this section we show that the “False Conjecture” is true whenever $`\lambda `$ is a rectangular shape.

Theorem 4.1. If $`\pi `$ is a permutation of rectangular shape $`(m^k)`$, and $`\mu `$ is an arbitrary shape, then:

$`\mu `$ is the shape of some subsequence of $`\pi `$ if and only if $`\mu (m^k)`$.

In order to prove Theorem 4.1 we need the following consequence of Greene’s Theorem.

Lemma 4.2. Let $`\pi `$ be a permutation of shape $`\lambda `$.

* If $`\pi `$ contains a disjoint union of $`k`$ increasing subsequences of lengths $`\mathrm{}_1\mathrm{}_2\mathrm{}\mathrm{}_k`$ then $`(\mathrm{}_1,\mathrm{},\mathrm{}_k)\lambda .`$
* If $`\pi `$ contains a disjoint union of $`k`$ decreasing subsequences of lengths $`\mathrm{}_1\mathrm{}_2\mathrm{}\mathrm{}_k`$ then $`(\mathrm{}_1,\mathrm{},\mathrm{}_k)\lambda ^{}.`$

Proof. By Greene’s Theorem, for any $`1ik`$

$$\underset{j=1}{\overset{i}{}}\mathrm{}_j\text{maximal size of a union of }i\text{ increasing subsequences of }\pi =\underset{j=1}{\overset{i}{}}\lambda _j.$$

The proof of the second part is similar.

$`\mathrm{}`$

The following lemma characterizes permutations having rectangular shape.

Lemma 4.3.

* A permutation $`\pi `$ has shape $`(m^k)`$ if and only if the following two conditions are simultaneously satisfied:

+ $`\pi `$ is a disjoint union of $`k`$ increasing subsequences, each of length $`m`$.
    + $`\pi `$ is a disjoint union of $`m`$ decreasing subsequences, each of length $`k`$.
* If the above conditions hold, then each of the $`k`$ increasing subsequences intersects each of the $`m`$ decreasing subsequences in exactly one element.

Proof.

(a) Assume that $`\pi `$ has shape $`\lambda `$ and satisfies conditions (a1) and (a2) of the Lemma. By (a1) and Lemma 4.2(a), $`(m^k)\lambda `$. By (a2) and Lemma 4.2(b), $`(k^m)\lambda ^{}`$. Also $`|\lambda |=|(m^k)|=km`$, so by Corollary 2.2, $`\lambda =(m^k)`$.

In the other direction: By Greene’s Theorem, if $`\pi `$ has shape $`(m^k)`$ then it is the disjoint union of $`k`$ increasing subsequences $`\alpha _1,\mathrm{},\alpha _k`$ of total size $`km`$. By Schensted’s Theorem, each increasing subsequence of $`\pi `$ has size at most $`m`$, and therefore $`|\alpha _1|=\mathrm{}=|\alpha _k|=m`$. Similarly, $`\pi `$ is a disjoint union of $`m`$ decreasing subsequences $`\beta _1,\mathrm{},\beta _m`$ satisfying $`|\beta _1|=\mathrm{}=|\beta _m|=k`$.

(b) Each increasing subsequence $`\alpha _i`$ intersects each decreasing subsequence $`\beta _j`$ in at most one element, and since these $`km`$ intersections cover all elements of $`\pi `$ they are all nonempty.

$`\mathrm{}`$

Proof of Theorem 4.1. Let $`\pi `$ be a sequence of shape $`\lambda =(m^k)`$. If $`\mu `$ is the shape of some subsequence of $`\pi `$ then this subsequence contains an increasing subsequence of length $`\mu _1`$. Therefore $`\mu _1\lambda _1=m`$. Similarly $`\mu _1^{}\lambda _1^{}=k`$, so that $`\mu (m^k)`$.

In the other direction: By Lemma 4.3, $`\pi `$ is a disjoint union of $`k`$ increasing subsequences, of length $`m`$ each, say $`\alpha _1,\mathrm{},\alpha _k`$ (enumerated arbitrarily). Similarly, $`\pi `$ is a disjoint union of $`m`$ decreasing subsequences, say $`\beta _1,\mathrm{},\beta _m`$ (of length $`k`$ each). Also, each $`\alpha _i`$ intersects each $`\beta _j`$ in a unique element; denote it by $`P(i,j)`$. Now let $`\mu (m^k)`$, and define $`\sigma `$ to be the subsequence of $`\pi `$ consisting of all elements $`P(i,j)`$ with $`j\mu _i`$. We claim that $`\sigma `$ has shape $`\mu `$.

Indeed, $`\sigma `$ intersects $`\alpha _i`$ in $`\mu _i`$ elements, and therefore (by Lemma 4.2(a)) $`\mu \mathrm{𝑠ℎ𝑎𝑝𝑒}(\sigma )`$. Similarly, $`\sigma `$ intersects $`\beta _j`$ in $`\mu _j^{}`$ elements, and therefore (by Lemma 4.2(b)) $`\mu ^{}\mathrm{𝑠ℎ𝑎𝑝𝑒}(\sigma )^{}`$. Since $`|\mathrm{𝑠ℎ𝑎𝑝𝑒}(\sigma )|=|\mu |`$ by definition, Corollary 2.2 implies that $`\mathrm{𝑠ℎ𝑎𝑝𝑒}(\sigma )=\mu `$ and the proof is complete.

$`\mathrm{}`$

The following theorem is complementary.

Theorem 4.4. If $`\pi `$ is a sequence of shape $`\lambda `$ and $`(m^k)\lambda `$, then there exists a subsequence of $`\pi `$ of shape $`(m^k)`$.

In other words: For any positive integers $`m`$ and $`k`$

$$\mathrm{𝐴𝑣𝑜𝑖𝑑}_n^{(m^k)}\underset{\{\lambda n|(m^k)\lambda \}}{}C^\lambda .$$

Note that Example 3.3 shows that the converse of Theorem 4.4 is false.

Proof. Let $`\pi `$ be a sequence of shape $`\lambda `$. By Greene’s Theorem, $`\pi `$ contains a disjoint union of $`k`$ increasing subsequences of total size $`_{j=1}^k\lambda _j`$. Denote this union by $`\overline{\pi }`$, and let $`\mu :=\mathrm{𝑠ℎ𝑎𝑝𝑒}(\overline{\pi })`$. Obviously, there are at most $`k`$ parts in $`\mu `$ (i.e., $`\mu =(\mu _1,\mathrm{},\mu _k)`$ with $`\mu _k0`$) and $`_{j=1}^k\mu _j=_{j=1}^k\lambda _j`$. By Greene’s Theorem,

$$\underset{j=1}{\overset{k1}{}}\mu _j=\text{maximal size of a union of }k1\text{ increasing subsequences in }\overline{\pi }$$

$$\text{maximal size of a union of }k1\text{ increasing subsequences in }\pi =\underset{j=1}{\overset{k1}{}}\lambda _j.$$

Hence, $`\mu _k\lambda _k`$. By assumption $`(m^k)\lambda `$, so that $`m\lambda _k`$. We conclude that there are exactly $`k`$ parts in $`\mu `$, and $`\mu _1\mathrm{}\mu _km`$. In other words, $`\mu _1^{}=k`$ and $`(k^m)\mu ^{}`$.

Now, by the second part of Greene’s Theorem, $`\overline{\pi }`$ contains a disjoint union of $`m`$ decreasing subsequences of total size $`km`$. Denote this union by $`\widehat{\pi }`$, and denote its shape by $`\nu `$. $`\widehat{\pi }`$ is a subsequence of $`\overline{\pi }`$, hence,

$$\nu _1^{}=\text{length of maximal decreasing subsequence in }\widehat{\pi }$$

$$\text{length of maximal decreasing subsequence in }\overline{\pi }=\mu _1^{}=k.$$

On the other hand,

$$|\nu |=\nu _1^{}+\mathrm{}+\nu _m^{}=km.$$

This shows that the shape of the subsequence $`\widehat{\pi }`$ is $`\nu =(m^k)`$.

$`\mathrm{}`$

## 5 General Shapes

Theorem 5.1. For any partition $`\mu =(\mu _1,\mathrm{},\mu _k)`$ of $`m`$ and any positive integer $`n`$,

$$\mathrm{𝐴𝑣𝑜𝑖𝑑}_n^\mu \underset{\{\lambda n|(\mu _1^k)\lambda \}}{}C^\lambda .$$
$`(5.1)`$   
Proof. Let $`\lambda `$ be a shape such that $`(\mu _1^k)\lambda `$. By Theorem 4.4, any permutation of shape $`\lambda `$ contains a subsequence of shape $`(\mu _1^k)`$. By Theorem 4.1, this subsequence contains a subsequence of shape $`\mu `$. $`\mathrm{}`$

Let $`\mathrm{𝑎𝑣𝑜𝑖𝑑}_n^\mu `$ be the size of the set $`\mathrm{𝐴𝑣𝑜𝑖𝑑}_n^\mu `$. Theorem 5.1 implies the following asymptotic estimates.

Corollary 5.2. For any fixed partition $`\mu =(\mu _1,\mathrm{},\mu _k)`$,

$$\underset{n\mathrm{}}{lim\; sup}(\mathrm{𝑎𝑣𝑜𝑖𝑑}_n^\mu )^{1/2n}\text{ht}(\mu )+\text{wd}(\mu )$$
$`(5.2)`$   
and

$$\mathrm{max}\{\text{ht}(\mu ),\text{wd}(\mu )\}\underset{n\mathrm{}}{lim\; inf}(\mathrm{𝑎𝑣𝑜𝑖𝑑}_n^\mu )^{1/2n},$$
$`(5.3)`$   
where the height of $`\mu `$ $`\text{ht}(\mu ):=\mu _1^{}1`$, and the width of $`\mu `$ $`\text{wd}(\mu ):=\mu _11`$.

Proof. Let $`\lambda `$ be a partition of $`n`$, and let $`f^\lambda `$ be the number of standard Young tableaux of shape $`\lambda `$. By the Robinson-Schensted correspondence

$$(f^\lambda )^2=\mathrm{\#}\{\pi S_n|\mathrm{𝑠ℎ𝑎𝑝𝑒}(\pi )=\lambda \}.$$

Combining this fact with Theorem 5.1 we obtain

$$\mathrm{𝑎𝑣𝑜𝑖𝑑}_n^\mu \mathrm{\#}\{\pi S_n|(\mu _1^k)\mathrm{𝑠ℎ𝑎𝑝𝑒}(\pi )\}=\underset{\lambda n(\mu _1^k)\lambda }{}(f^\lambda )^2.$$

The asymptotics of the sum on the right hand side was studied by Berele and Regev \[BR, Section 7\]. By \[BR, Theorem 7.21\], for fixed $`\mu _1`$ and $`k`$

$$\underset{\lambda n(\mu _1^k)\lambda }{}(f^\lambda )^2c_1(\mu _1,k)n^{c_2(\mu _1,k)}(\mu _1+k2)^{2n},$$
$`(5.4)`$   
when $`n`$ tends to infinity. Here $`c_1(\mu _1,k)`$ and $`c_2(\mu _1,k)`$ are independent of $`n`$. This proves the upper bound (5.2).

For the lower bound, note that by Schensted’s Theorem any permutation avoiding $`(\mu _1)`$ also avoids $`\mu `$. Similarly, any permutation avoiding $`(1^k)`$ also avoids $`\mu `$. Thus

$$\mathrm{𝐴𝑣𝑜𝑖𝑑}_n^{(\mu _1)}\mathrm{𝐴𝑣𝑜𝑖𝑑}_n^{(1^{\mu _1^{}})}\mathrm{𝐴𝑣𝑜𝑖𝑑}_n^\mu .$$

This implies that (for $`n`$ large enough; e.g., $`n>(\mu _11)(\mu _1^{}1)`$ )

$$\mathrm{𝑎𝑣𝑜𝑖𝑑}_n^{(\mu _1)}+\mathrm{𝑎𝑣𝑜𝑖𝑑}_n^{(1^{\mu _1^{}})}\mathrm{𝑎𝑣𝑜𝑖𝑑}_n^\mu .$$

Combining this inequality with (5.4) proves the lower bound (5.3).

$`\mathrm{}`$

Note: For an evaluation of $`\mathrm{𝑎𝑣𝑜𝑖𝑑}_n^{(m)}`$ for $`m4`$ see \[St Exer. 7.16(e)\]. An asymptotic evaluation of $`\mathrm{𝑎𝑣𝑜𝑖𝑑}_n^{(m)}`$ for fixed $`m>4`$ was first done in \[Re\].

## 6 Other Special Cases

### 6.1 Hooks

In this subsection we show that for hook avoiding permutations and $`n`$ large enough the “False Conjecture” is correct.

Theorem 6.1. For any hook $`\mu =(m,1^{k1})`$ and $`n>(2m4)(2k4)`$

$$\mathrm{𝐴𝑣𝑜𝑖𝑑}_n^{(m,1^{k1})}=\underset{\{\lambda n|(m,1^{k1})\lambda \}}{}C^\lambda .$$

Note: If either $`m3`$ or $`k3`$ then equality holds for all values of $`n`$.

The following analogue of Lemma 4.3 characterizes permutations of hook shape.

Lemma 6.2. A permutation $`\pi `$ has shape $`(m,1^{k1})`$ if and only if $`\pi `$ is a union of an increasing subsequence of length $`m`$ and a decreasing subsequence of length $`k`$, intersecting in a unique element.

Proof. By Schensted’s Theorem, a permutation $`\pi `$ of shape $`(m,1^{k1})`$ contains an increasing subsequence $`\alpha `$ with $`|\alpha |=m`$ and a decreasing subsequence $`\beta `$ with $`|\beta |=k`$, where $`|\alpha \beta ||\pi |=m+k1`$. Since necessarily $`|\alpha \beta |1`$, it follows that $`|\alpha \beta |=1`$.

The converse follows similarly from Schensted’s Theorem.

$`\mathrm{}`$

Lemma 6.3. Let $`m`$ and $`k`$ be positive integers.

* If either $`m3`$ or $`k3`$ then every permutation whose shape contains the hook $`(m,1^{k1})`$ has a subsequence of shape $`(m,1^{k1})`$.
* If $`m4`$ and $`k4`$ then every permutation whose shape contains the hook $`(2m3,1^{k1})`$ or the hook $`(m,1^{2k4})`$ has a subsequence of shape $`(m,1^{k1})`$.
* For any $`m4`$ and $`k4`$ there exists a permutation whose shape contains $`(2m4,1^{2k5})`$, but it has no subsequence of shape $`(m,1^{k1})`$.

Note: The results in (a) and (b) above are best possible, as far as the assumed size of a hook contained in the shape is concerned. For (a) this is clear, and for (b) this is the content of (c).

Proof. We shall prove (b); the proof of (a) is similar.

(b) Let $`\pi `$ be a permutation whose shape contains the hook $`(2m3,1^{k1})`$, with $`m,k4`$. Then $`\pi `$ has an increasing subsequence $`\alpha `$ of length $`2m3`$ and a decreasing subsequence $`\beta `$ of length $`k`$. If $`\alpha `$ and $`\beta `$ intersect (necessarily in a unique element), then by truncating $`\alpha `$ to $`m`$ elements we get by Lemma 6.2 a subsequence of shape $`(m,1^{k1})`$. Otherwise (i.e., assuming that $`\alpha `$ and $`\beta `$ do not intersect) we will show that the union of $`\alpha `$ and $`\beta `$ contains the required subsequence.

Let $`\alpha =(\alpha _1,\mathrm{},\alpha _{2m3})`$ and $`\beta =(\beta _1,\mathrm{},\beta _k)`$, so that $`\alpha _1<\mathrm{}<\alpha _{2m3}`$ and $`\beta _1>\mathrm{}>\beta _k`$.

Let $`\mathrm{𝑖𝑛𝑑}(\alpha _i)`$ denote the index of $`\alpha _i`$ in the union of $`\alpha `$ and $`\beta `$ (as a subsequence of $`\pi `$); similarly for $`\mathrm{𝑖𝑛𝑑}(\beta _j)`$.

Concerning the element $`\alpha _{m1}`$ there are three possibilities:

* There is an index $`1jk1`$ such that

$$\mathrm{𝑖𝑛𝑑}(\beta _j)<\mathrm{𝑖𝑛𝑑}(\alpha _{m1})<\mathrm{𝑖𝑛𝑑}(\beta _{j+1}).$$
* $`\mathrm{𝑖𝑛𝑑}(\alpha _{m1})<\mathrm{𝑖𝑛𝑑}(\beta _1).`$
* $`\mathrm{𝑖𝑛𝑑}(\alpha _{m1})>\mathrm{𝑖𝑛𝑑}(\beta _k).`$

We shall deal with case (1); the other cases are similar. Since $`\beta _j>\beta _{j+1}`$, there are now three subcases:

* $`\beta _j>\alpha _{m1}>\beta _{j+1}.`$
* $`\alpha _{m1}<\beta _{j+1}.`$
* $`\alpha _{m1}>\beta _j.`$

In case (1a), $`\alpha _{m1}`$ may be added to the decreasing subsequence $`\beta `$, to obtain two intersecting monotone subsequences of lengths $`2m3`$ and $`k+1`$. By truncating these subsequences we will get an increasing subsequence of length $`m`$ intersecting a decreasing subsequence of length $`k`$.

In case (1b), $`(\alpha _1,\mathrm{},\alpha _{m1},\beta _{j+1})`$ is an increasing subsequence of length $`m`$ intersecting $`\beta `$.

In case (1c), $`(\beta _j,\alpha _{m1},\alpha _m,\mathrm{},\alpha _{2m3})`$ is an increasing subsequence of length $`m`$ intersecting $`\beta `$.

By Lemma 6.2, in all cases we obtain a subsequence of $`\pi `$ having shape $`(m,1^{k1})`$.

(c) The construction extends Example 3.2 (for which $`m=k=4`$): take $`\pi =(\gamma ,\alpha ,\delta ,\beta )`$, where $`\alpha `$ and $`\delta `$ are increasing sequences of length $`m2`$ and $`\beta ,\gamma `$ are decreasing sequences of length $`k2`$:

$$\alpha =(1,\mathrm{},m2);\beta =(m+k4,\mathrm{},m1);$$

$$\gamma =(m+2k6,\mathrm{},m+k3);\delta =(m+2k5,\mathrm{},2m+2k8).$$

It is easy to see that an increasing subsequence of $`\pi `$ intersecting $`\gamma `$ must be contained (omitting the intersection element itself) in $`\delta `$, so that its total length is at most $`m1`$. Similar analysis of $`\beta `$ shows that an increasing subsequence of length $`m`$ in $`\pi `$ must be contained in $`(\alpha ,\delta )`$. Analogously, a decreasing subsequence of length $`k`$ must be contained in $`(\gamma ,\beta )`$. The two subsequences cannot intersect.

$`\mathrm{}`$

Proof of Theorem 6.1. By Schensted’s Theorem, if a permutation $`\pi `$ has a subsequence of shape $`(m,1^{k1})`$ then it has an increasing subsequence of length $`m`$ and a decreasing subsequence of length $`k`$. On the other hand, a permutation in $`_{\{\lambda n|(m,1^{k1})\lambda \}}C^\lambda `$ has either no increasing subsequence of length $`m`$ or no decreasing subsequence of length $`k`$. Thus,

$$\underset{\{\lambda n|(m,1^{k1})\lambda \}}{}C^\lambda \mathrm{𝐴𝑣𝑜𝑖𝑑}_n^{(m,1^{k1})}.$$

For the other direction, assume that $`\pi C^\lambda `$ with $`(m,1^{k1})\lambda `$. Hence, $`\lambda _1m`$ and $`\lambda _1^{}k`$. If either $`m3`$ or $`k3`$ then, by Lemma 6.3(a), $`\pi `$ has a subsequence of shape $`(m,1^{k1})`$. Otherwise (i.e., if $`m4`$ and $`k4`$), by assumption $`(2m4)(2k4)<n=|\lambda |\lambda _1\lambda _1^{}`$, and therefore either $`\lambda _1>2m4`$ or $`\lambda _1^{}>2k4`$. We can now use Lemma 6.3(b).

$`\mathrm{}`$

Corollary 6.4. For any pair of positive integers $`m`$ and $`k`$, and for $`n4mk`$

$$\mathrm{𝑎𝑣𝑜𝑖𝑑}_n^{(m,1^{k1})}=\mathrm{𝑎𝑣𝑜𝑖𝑑}_n^{(m)}+\mathrm{𝑎𝑣𝑜𝑖𝑑}_n^{(1^k)}=\underset{\lambda n\lambda _1<m}{}(f^\lambda )^2+\underset{\lambda n\lambda _1^{}<k}{}(f^\lambda )^2,$$

where $`f^\lambda `$ is the number of standard Young tableaux of shape $`\lambda `$.

Combining Corollary 6.4 with (5.4) we obtain

Corollary 6.5.

$$\underset{n\mathrm{}}{lim}(\mathrm{𝑎𝑣𝑜𝑖𝑑}_n^{(m,1^{k1})})^{1/2n}=\mathrm{max}\{m1,k1\}.$$

### 6.2 Avoiding $`(2^2)`$

In this subsection we compute $`\mathrm{𝑎𝑣𝑜𝑖𝑑}_n^{(2^2)}`$ and show that

$$\underset{n\mathrm{}}{lim}(\mathrm{𝑎𝑣𝑜𝑖𝑑}_n^{(2^2)})^{1/2n}=\sqrt{2+\sqrt{2}}.$$

In particular, unlike the case of hooks, neither the lower bound nor the upper bound of Corollary 5.2 gives the correct limit in this case.

Example 3.3 shows that for any $`n5`$,

$$\underset{\{\lambda n|(2^2)\lambda \}}{}C^\lambda \mathrm{𝐴𝑣𝑜𝑖𝑑}_n^{(2^2)}.$$

However, the opposite inclusion does hold.

Proposition 6.6. For any positive $`n`$,

$$\mathrm{𝐴𝑣𝑜𝑖𝑑}_n^{(2^2)}\underset{\{\lambda n|(2^2)\lambda \}}{}C^\lambda .$$

Proposition 6.6 is a special case of Theorem 4.4. Here we suggest an independent and more informative proof of this result.

Proof. By induction on $`n`$. The claim obviously holds for $`n4`$. Assume that it holds for $`n1`$, for some $`n5`$.

For the induction step observe that $`C^{(2^2)}=\{2143,2413,3142,3412\}`$ consists of all permutations in $`S_4`$ for which 1 and 4 are in the ‘middle’. It follows that for any permutation $`\pi `$ in $`S_n`$, if $`\pi _1\{1,n\}`$ and $`\pi _n\{1,n\}`$ then $`\pi `$ is not $`(2^2)`$-avoiding. Therefore, if $`\pi S_n`$ is $`(2^2)`$-avoiding then either

$`\pi _1\{1,n\}`$ or $`\pi _n\{1,n\}`$. Assume that $`\pi _1\{1,n\}`$. By the induction hypothesis the shape of the subsequence $`(\pi _2,\mathrm{},\pi _n)`$ does not contain $`(2^2)`$ and is therefore a hook $`(r,1^{nr1})`$ for some $`1rn1`$. Adding $`\pi _1=1`$ increases the size of the longest increasing subsequence by 1; thus, by Schensted’s Theorem the resulting shape is $`(r+1,1^{nr1})`$. Adding $`\pi _1=n`$ increases the size of the longest decreasing subsequence by 1; again, by Schensted’s Theorem the resulting shape is $`(r,1^{nr})`$. The case $`\pi _n\{1,n\}`$ is similar.

$`\mathrm{}`$

Corollary 6.7. For any positive integer $`n`$

$$\mathrm{𝑎𝑣𝑜𝑖𝑑}_n^{(2^2)}=\frac{1}{2}(2+\sqrt{2})^{n1}+\frac{1}{2}(2\sqrt{2})^{n1}.$$

Proof. It follows from the proof of Proposition 6.6 that

$$\mathrm{𝑎𝑣𝑜𝑖𝑑}_n^{(2^2)}=4\mathrm{𝑎𝑣𝑜𝑖𝑑}_{n1}^{(2^2)}2\mathrm{𝑎𝑣𝑜𝑖𝑑}_{n2}^{(2^2)}.$$

The solution of this linear recursion (with appropriate initial values) gives the desired result.

$`\mathrm{}`$

## 7 Final Remarks and Open Problems

### 7.1 Algebraic Structure

Let $`R`$ be the set of all representatives of minimal length of left cosets of $`S_m`$ in $`S_n`$ (length here, as usual, is in terms of the Coxeter generators, i.e., adjacent transpositions). For any partition $`\mu `$ of $`m`$, the set $`C^\mu `$ of all permutations of shape $`\mu `$ is a two-sided Kazhdan-Lusztig cell in $`S_m`$. For any $`nm`$ the set of all permutations in $`S_n`$ which are not $`\mu `$-avoiding coincides with the set $`RC^\mu R^1`$. Theorem 5.1 claims that for hook shapes the set $`RC^\mu R^1`$ is a union of two-sided Kazhdan-Lusztig cells. This phenomenon generalizes a beautiful well-known fact: The set $`RC^\mu `$ (or: $`C^\mu R^1`$) is a union of Kazhdan-Lusztig left (resp. right) cells \[Sr, BV Prop. 3.15\]. See also \[GaR, Ro\]. Barbasch and Vogan gave an algebraic proof of this fact by associating the set $`RC^\mu `$ to induced representations. An algebraic interpretation for the results in this paper is required. These and other relations with representation theory deserve further study.

### 7.2 Asymptotics

Regev calculated, by considering Schensted’s Theorem, the exact asymptotics of $`\mathrm{𝑎𝑣𝑜𝑖𝑑}_n^{(m)}`$ \[Re\]. In this paper we have generalized this “RSK approach” to prove that for any partition $`\mu `$ there exists a constant $`c(\mu )`$ such that, for any $`n`$,

$$\mathrm{𝑎𝑣𝑜𝑖𝑑}_n^\mu c(\mu )^n.$$

Note that from Corollary 5.2 and Corollary 6.7 it also follows that, for $`\mu `$ not strictly contained in $`(2^2)`$, there exists a constant $`\stackrel{~}{c}(\mu )>1`$ such that $`\mathrm{𝑎𝑣𝑜𝑖𝑑}_n^\mu \stackrel{~}{c}(\mu )^n`$ for $`n`$ large enough.

A far reaching generalization was conjectured by Stanley and Wilf \[Bo1\].

The Stanley-Wilf Conjecture. For any fixed permutation $`\sigma `$ there exists a constant $`c(\sigma )`$ such that, for any $`n`$

$$\mathrm{𝑎𝑣𝑜𝑖𝑑}_n(\sigma )c(\sigma )^n,$$

where $`\mathrm{𝑎𝑣𝑜𝑖𝑑}_n(\sigma )`$ is the number of all $`\sigma `$-avoiding permutations in $`S_n`$.

By a result of Arratia \[Ar\], if this conjecture holds then actually the limit $`lim_n\mathrm{}\mathrm{𝑎𝑣𝑜𝑖𝑑}_n(\sigma )^{1/n}`$ always exists (and is finite).

The Stanley-Wilf conjecture holds for all $`\sigma S_3`$ \[K, p. 238\] and all $`\sigma S_4`$ \[Bo1, Bo2\], as well as for many other cases (see \[SSi\], \[Bo3\] and their references). Recently, Alon and Friedgut \[AF\] have applied Davenport-Schinzel sequences to prove a somewhat weaker version of the conjecture for arbitrary $`\sigma `$. An interesting challenge is to apply the “RSK approach” to attack the Stanley-Wilf Conjecture; namely, to apply Greene’s Theorem and methods presented in this paper to sets avoiding a single permutation.

Acknowledgments. The authors thank Noga Alon, Miklos Bóna, Ehud Friedgut, Nati Linial, Alek Vainshtein and Julian West for useful discussions. Special thanks to Amitai Regev for stimulating comments.