Consider a permutation of letters written in one line notation, say . An increasing subsequence of is a choice of integers such that , a decreasing subsequence is defined analogously. Show that any permutation in letters has either an increasing subsequence of length or a decreasing subsequence of length . Is the bound optimal?

Advertisements