On weak twins and up-and-down subpermutations

Two permutations (x 1 , . . . , x w ) and (y 1 , . . . , 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 π be a permutation of the set [n] = {1, 2, . . . , n} and let wt(π) denote the largest integer w such that π contains a pair of disjoint weakly similar subpermutations (called weak twins) of length w. Finally, let wt(n) denote the minimum of wt(π) over all permutations π of [n]. Clearly, wt(n) ≤ n/2. In this paper, we show that n/12 ≤ wt(n) ≤ n/2 − Ω(n 1/3 ). We also study a variant of this problem. Let us say that (π(i 1 ), . . . , π(i j )), i 1 < ⋅ ⋅ ⋅ < i j , is an alternating (or up-and-down) subpermutation of π if π(i 1 ) > π(i 2 ) < π(i 3 ) > ⋅ ⋅ ⋅ or π(i 1 ) < π(i 2 ) > π(i 3 ) < ⋅ ⋅ ⋅. Let Π n be a random permutation selected uniformly from all n! permutations of [n]. Stanley has shown that the length of a longest alternating permutation in Π n is asymptotically almost surely (a. a. s.) close to 2n/3. We study the maximum length α(n) of a pair of disjoint alternating sub-permutations in Π n and show that there are two constants 1/3 < c 1 < c 2 < 1/2 such that a. a. s. c 1 n ≤ α(n) ≤ c 2 n. In addition, we show that the alternating shape is the most popular among all permutations of a given length.