# Decomposition of a permutation into increasing subsequences

Given a permutation $$P$$, the goal is to decompose this permutation into $$k$$ increasing subsequences $$L_1,L_2,\ldots,L_k$$, such that every element in $$P$$ appears exactly once in some increasing subsequence and one cannot decompose $$P$$ into $$k' increasing subsequences. $$|L_1|\geq |L_2|\ldots \geq |L_k|$$.

The value $$k$$ is known to be length of the longest decreasing subsequence in $$P$$.

There may be several decompositions of $$P$$, however a decomposition $$L_1,\dots,L_k$$ is said to be an ideal decomposition if for every $$i\le k$$ and every disjoint increasing subsequences $$L'_1,\dots,L'_i$$, we have $$|L'_1|+\dots+|L'_i|\le|L_1|+\dots+|L_i|$$.

(Question a):- How much time is needed to find an ideal decomposition?

Example :- Say the permutation $$P=[1,7,8,2,9,3,6,5,4]$$.

Then

$$L_1= 1,7,8,9$$

$$L_2=2,3,6$$

$$L_3=5$$

$$L_4=4$$

$$P$$ cannot be decomposed into 3 or lesser increasing subsequences, because it contains the subsequence 9654 and no two of these integers can belong to the same increasing subsequence.

$$L_1,L_2,L_3,L_4$$ is an ideal decomposition of $$P$$, because

1. if we have to choose only one increasing subsequence from $$P$$, then its maximum length is $$|L_1|=4$$
2. if we have to choose only two increasing subsequences from $$P$$, then their maximum total length is $$|L_1+L_2|=7$$ ... and so on.

$$P$$ also has another ideal decomposition which is as follows

$$L_1= 1,2,3,6$$

$$L_2=7,8,9$$

$$L_3=5$$

$$L_4=4$$

Bonus question:- Can this ideal decomposition be maintained dynamically in $$o(n)$$ time under insertion of the following type.

If $$|P|=n$$, then $$n+1$$ is inserted in $$P$$ (to get $$P'$$) possibly at any index and data structure would now reflect the new ideal decomposition of $$P'$$. Initially $$P=1$$. For example if $$P=[1,7,8,2,9,3,6,5,4]$$, then $$P'$$ can be [1,7,$$\textbf{10}$$,8,2,9,3,6,5,4]

This question is closely related to Young's tableau and Greene's theorem. I believe that this might be a well studied problem. Just need some references. Thanks in advance.

• I can't make any sense of the definition. What does $L_1\ge L_2\ge\dots$ mean? What does it mean "if we need to choose" - choose for what purpose? Why would we need to do that? What does it mean "choosing the list $L_1,\dots,L_i$ would maximize the sum $L_1+\dots+L_k$" - is the $L_1,\dots,L_i$ a different list from the "ideal one"? If so, why does $L_1+\dots+L_k$ end in $L_k$ rather than $L_i$? What properties the newly chosen list has to satisfy? And what does $L_1+\dots+L_k$ mean in the first place? I'm completely lost. Commented Jul 16, 2022 at 8:22
• If this is a previously studied problem, please give a reference to a comprehensible definition. Commented Jul 16, 2022 at 9:14
• @ Emil:- The related problem of LIS and Young's tableau have been quite well-studied. William Fulton wrote a textbook on Young's tableau which captures a lot of the topics mentioned above. I have also explained the example and clarified the notation abuse. $L_1$ was referring to the increasing subsequence as well as its length. I have rectified that abuse. "need to choose", because there is a correspondence between this type of definition for ideal decomposition and the structure of a Young's tableau constructed from a permutation $P$ using Schensted's insertion.
– Vk1
Commented Jul 16, 2022 at 12:19
• I tried to guess the intended definition of ideal decomposition from the example, and edited the post accordingly. Let me know if I misunderstood anything. Commented Jul 16, 2022 at 14:48
• Thank you for the clarifications Prof Emil Jerabek, however Prof Peter Shor figured out that my question was wrong. However, I am grateful for your time.
– Vk1
Commented Jul 16, 2022 at 17:49

You seem to be assuming that an ideal decomposition exists for all permutations. It does not.

Consider the permutation

6 2 4 8 10 1 3 7 9 5.

The maximum length increasing subsequence is 4. If you take
$$L_1$$ = 2 4 8 10,
$$L_2$$ = 1 3 7 9,
then you get $$| L_1 + L_2| = 8.$$

This is the only way of getting two increasing subsequences whose lengths add to $$8$$, because neither $$6$$ nor $$5$$ can be in an increasing subsequence of length 4.

You can also decompose the whole permutation into three increasing subsequences

$$M_1$$ = 6 8 10,
$$M_2$$ = 2 4 7 9,
$$M_3$$ = 1 3 5.

But it is impossible to add an increasing subsequence of length $$2$$ to the subsequences $$L_1$$ and $$L_2$$.

If ideal decompositions of permutations into increasing subsequences existed for all permutations, they would probably be well-studied. However, they don't.

You could ask for an algorithm to determine whether an ideal decomposition exists, and if it does, to find one. I don't know if you would be interested in such an algorithm, or whether this problem has been studied. In any case, this would probably be better posed in a new cstheory.SE question rather than editing this one.

• Never been so happy to be wrong. Thank you Professor Peter Shor.
– Vk1
Commented Jul 16, 2022 at 17:42