On weak twins and up-and-down sub-permutations

Abstract

Two permutations $(x_1,\dots ,x_w)$ and $(y_1,\dots ,y_w)$ are weakly similar if $x_i<x_{i+1}$ if and only if $y_i<y_{i+1}$ for all $1⩽i⩽w$. Let $\pi$ be a permutation of the set $[n]=\{1,2,\dots ,n\}$ and let $wt(\pi )$ denote the largest integer $w$ such that $\pi$ contains a pair of disjoint weakly similar sub-permutations (called weak twins) of length $w$. Finally, let $wt(n)$ denote the minimum of $wt(\pi )$ over all permutations $\pi$ of $[n]$. Clearly, $wt(n)\le n/2$. In this paper we show that $\frac{n}{12}\le wt(n)\le \frac{n}{2}-\Omega (n^{1/3})$. We also study a variant of this problem. Let us say that ${\pi }^{\prime }=(\pi (i_1),...,\pi (i_j))$, $i_1<\cdots <i_j$, is an alternating (or up-and-down) sub-permutation of $\pi$ if $\pi (i_1)>\pi (i_2)<\pi (i_3)>...$ or $\pi (i_1)<\pi (i_2)>\pi (i_3)<...$. Let ${\Pi }_n$ be a random permutation selected uniformly from all $n!$ permutations of $[n]$. It is known that the length of a longest alternating permutation in ${\Pi }_n$ is asymptotically almost surely (a.a.s.) close to $2n/3$. We study the maximum length $\alpha (n)$ of a pair of disjoint alternating sub-permutations in ${\Pi }_n$ and show that there are two constants $1/3<c_1<c_2<1/2$ such that a.a.s. $c_{1}n\le \alpha (n)\le c_{2}n$. In addition, we show that the alternating shape is the most popular among all permutations of a given length.