On weak twins and up-and-down subpermutations
Andrzej Dudek, Jarosław Grytczuk, Andrzej Ruciński · 2022
Two permutations (x 1 , . . . , x w ) and (y 1 , . . . , y w ) are weakly similar if x i π(i 2 ) ⋅ ⋅ ⋅ or π(i 1 ) π(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.