Avoidance of two permutations

Let $1 \leq m \leq n, \sigma \in S_n, \pi \in S_m$. The permutation $\sigma$ avoids $\pi$ if no subset $\{j_1 < \cdots < j_m\} \subseteq \{1,\cdots,n\}$ exists, so that for all $1 \leq i < l \leq m$ applies $$\sigma(j_i) < \sigma(j_l) \Leftrightarrow \pi(i) < \pi(l)$$

Prove that if a permutation $\sigma \in S_n$ avoids the permutation 123 it avoids the permutation 3124 as well (one-line-notation used for permutations).

Hi!

I first reflected on what the definition of the avoiding implies for $\sigma$ (apart from $|3124| = m = 4 \Rightarrow n \geq 4$). The only fact I discovered is that according to the definition $\sigma$ contains one ascension at most and this should "cover" the last part $124$ of $3124$.

• Summarizing the answers below: 3124 contains a copy of 123. – Yuval Filmus Jun 25 '11 at 23:29

Note that $\sigma$ fails to avoid $123$ iff $\sigma$ contains $123$ as a pattern, i.e., iff there are $1 \le i < j < k \le n$ such that $\sigma(i) < \sigma(j) < \sigma(k)$. Similarly, $\sigma$ fails to avoid $3124$ iff there are $1 \le i_1 < i_2 < i_3 < i_4 \le n$ such that $\sigma(i_2) < \sigma(i_3) < \sigma(i_1) < \sigma(i_4)$. But in that case $\sigma(i_2)\sigma(i_3)\sigma(i_4)$ is an instance of the pattern $123$ in $\sigma$, and $\sigma$ fails to avoid $123$ as well.

• @brian-m-scott thanks! – muffel Jun 26 '11 at 8:27
• @brian-m-scott I just thought about it again. You said that if $\sigma$ fails to avoid 123 it fails to avoid 3124 as well. But does this imply that if $\sigma$ avoids 123 it avoids 3124 as well? – muffel Jun 26 '11 at 18:26
• @muffel: Read more carefully. That's not what he said. – trutheality Jun 26 '11 at 19:11
• @trutheality you are right, sorry. my fault... – muffel Jun 26 '11 at 21:25

Intuitively, $\sigma$ avoids $\pi$ if it is impossible to apply the $\pi$ to $m$ objects as follows:

• Add $n-m$ objects to your ordered collection preserving the relative order of the original $m$ objects
• Apply $\sigma$
• Remove the objects you added.

Observation: $3124$ does not avoid $123$:

$123$ rearranges $ABC$ into $ABC$. We can add $X$ to get $XABC$, apply $3124$ to get $ABXC$, remove $X$ and get $ABC$.

I hope that intuition helps you move forward.

Also notice that $1234$ avoids $3124$ (trivial: different permutations of the same size avoid each other), but doesn't avoid $123$.