Prove that the longest decreasing subsequence of $p$ consists of $d$ elements.

Question

Let $p$ be a permutation and let $d$ be the smallest integer so that $p$ can be written as the union of $d$ increasing subsequences. Prove that the longest decreasing subsequence of $p$ consists of $d$ elements.

I just need a hint, please don't do the whole question for me. I'm just struggling on how to approach this question.

Thank you!

Answer 1

Hint: Show that this is a special case of the Dilworth's Theorem.

Answer 2

Well, let us see. Since p is a permutation, everything in it is distinct, unless I am misinterpreting.

I have more or less an exact answer.

Here is the hints for them.

a) It should be obvious that the longest decreasing subsequence cannot have more than d elements.

b) Next, you split p into d increasing subsequences, in the most intuitive way possible. If something can be put into the first subsequence, put it there. You want to show that this division creates the least number of increasing subsequences. (I did not prove it, but it seems obvious.) Afterwards, you want to show that you can find a decreasing subsequence from this division, such that there is one element from every increasing subsequence.

Here is the exact answer.

Consider a longest decreasing subsequence.

Can it be more than d elements?

Let the longest decreasing subsequence be 9 7 4 3 2. Can p be written as a union of, say, 4 increasing subsequences? No. the 7 must belong to a different one than the 9. The 4 must belong to a different one than the 7, and so on.

So, can it be less than d elements?

First of all, we can make the d subsequences distinct. In other words, no element is in 2 of them.

So, we have our permutation p = $e_1e_2...$, and we divide it into increasing subsequence as follows.

$e_1$ is $a_1$. For each $e_i$, go in order. Is it higher than the last element of $a_1$, if so, it is in $a_1$. If not, is it higher than the last element of $a_2$? If so, put it in $a_2$. If it is not higher than all the current subsequences, make a new one.

I claim that this division creates the least number of increasing subsequences. Prove it. Let the number be $d$.

Now, I want to find a decreasing subsequence. I claim that I can find a decreasing subsequence of at least d. Here is how I do it.

the last element, $l_d$ of the subsequence is the first element of $a_d$. Now, there must be an element of $a_{d-1}$ before $a_d$. Take the last element of $a_{d-1}$ that is before $l_{d}$. I claim that this element is bigger than $a_d$. If not, then $l_d$ should be in $a_{d-1}$ or $a_{d-2}$, etc. Continue until $a_1$, and now you have a decreasing subsequence of length d.