One too many

Consider a permutation \sigma of mn+1 letters written in one line notation, say \sigma = a_1\ldots a_{mn+1}. An increasing subsequence of \sigma is a choice of integers i_1 <\cdots < i_k such that a_{i_1}< \cdots < a_{i_k}, a decreasing subsequence is defined analogously. Show that any permutation in mn+1 letters has either an increasing subsequence of length n+1 or a decreasing subsequence of length m+1. Is the bound optimal?

Advertisements
One too many

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s