On the Longest $k$-Alternating Subsequence

Igor Pak, Robin Pemantle

Abstract


We show that the longest $k$-alternating substring of a random permutation has length asymptotic to $2(n-k)/3$.


Full Text: PDF