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