<p>You seem to be assuming that an ideal decomposition exists for all permutations. It does not.</p>
<p>Consider the permutation</p>
<p>6 2 4 8 10 1 3 7 9 5.</p>
<p>The maximum length increasing subsequence is 4. If you take<br />
<span class="math-container">$L_1$</span> = 2 4 8 10,<br />
<span class="math-container">$L_2$</span> = 1 3 7 9,<br />
then you get <span class="math-container">$| L_1 + L_2| = 8.$</span></p>
<p>This is the only way of getting two increasing subsequences whose lengths add to <span class="math-container">$8$</span>, because neither <span class="math-container">$6$</span> nor <span class="math-container">$5$</span> can be in an increasing subsequence of length 4.</p>
<p>You can also decompose the whole permutation into three increasing subsequences</p>
<p><span class="math-container">$M_1$</span> = 6 8 10,<br />
<span class="math-container">$M_2$</span> = 2 4 7 9,<br />
<span class="math-container">$M_3$</span> = 1 3 5.</p>
<p>But it is impossible to add an increasing subsequence of length <span class="math-container">$2$</span> to the subsequences <span class="math-container">$L_1$</span> and <span class="math-container">$L_2$</span>.</p>
<p>If ideal decompositions of permutations into increasing subsequences existed for all permutations, they would probably be well-studied. However, they don't.</p>
<p>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.</p>

CC BY-SA 4.0
2022-07-16T17:42:00.273Z
Never been so happy to be wrong.
Thank you Professor Peter Shor.
Vk1
CC BY-SA 4.0
2022-07-16T13:45:44.683Z
2022-07-17T15:31:54.610Z
2022-07-17T15:31:54.610Z
Peter Shor 
<p>Given a permutation <span class="math-container">$P$</span>, the goal is to decompose this permutation into <span class="math-container">$k$</span> increasing subsequences <span class="math-container">$L_1,L_2,\ldots,L_k$</span>, such that every element in <span class="math-container">$P$</span> appears exactly once in some increasing subsequence and one cannot decompose <span class="math-container">$P$</span> into <span class="math-container">$k'&lt;k$</span> increasing subsequences. <span class="math-container">$|L_1|\geq |L_2|\ldots \geq |L_k|$</span>.</p>
<p>The value <span class="math-container">$k$</span> is known to be length of the longest decreasing subsequence in <span class="math-container">$P$</span>.</p>
<p>There may be several decompositions of <span class="math-container">$P$</span>, however a decomposition <span class="math-container">$L_1,\dots,L_k$</span> is said to be an <em>ideal decomposition</em> if for every <span class="math-container">$i\le k$</span> and every disjoint increasing subsequences <span class="math-container">$L'_1,\dots,L'_i$</span>, we have <span class="math-container">$|L'_1|+\dots+|L'_i|\le|L_1|+\dots+|L_i|$</span>.</p>
<p><strong>(Question a):- How much time is needed to find an ideal decomposition?</strong></p>
<p>Example :-
Say the permutation <span class="math-container">$P=[1,7,8,2,9,3,6,5,4]$</span>.</p>
<p>Then</p>
<p><span class="math-container">$L_1= 1,7,8,9$</span></p>
<p><span class="math-container">$L_2=2,3,6$</span></p>
<p><span class="math-container">$L_3=5$</span></p>
<p><span class="math-container">$L_4=4$</span></p>
<p><span class="math-container">$P$</span> 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.</p>
<p><span class="math-container">$L_1,L_2,L_3,L_4$</span> is an ideal decomposition of <span class="math-container">$P$</span>, because</p>
<ol>
<li>if we have to choose only one increasing subsequence from <span class="math-container">$P$</span>, then its maximum length is <span class="math-container">$|L_1|=4$</span></li>
<li>if we have to choose only two increasing subsequences from <span class="math-container">$P$</span>, then their maximum total length is <span class="math-container">$|L_1+L_2|=7$</span>
...
and so on.</li>
</ol>
<p><span class="math-container">$P$</span> also has another ideal decomposition which is as follows</p>
<p><span class="math-container">$L_1= 1,2,3,6$</span></p>
<p><span class="math-container">$L_2=7,8,9$</span></p>
<p><span class="math-container">$L_3=5$</span></p>
<p><span class="math-container">$L_4=4$</span></p>
<p><strong>Bonus question:- Can this ideal decomposition be maintained dynamically in <span class="math-container">$o(n)$</span> time under insertion of the following type.</strong></p>
<p>If <span class="math-container">$|P|=n$</span>, then <span class="math-container">$n+1$</span> is inserted in <span class="math-container">$P$</span> (to get <span class="math-container">$P'$</span>) possibly at any index and data structure would now reflect the new ideal decomposition of <span class="math-container">$P'$</span>. Initially <span class="math-container">$P=1$</span>.
For example if <span class="math-container">$P=[1,7,8,2,9,3,6,5,4]$</span>, then <span class="math-container">$P'$</span> can be [1,7,<span class="math-container">$\textbf{10}$</span>,8,2,9,3,6,5,4]</p>
<p>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.</p>

CC BY-SA 4.0
2022-07-16T08:22:39.863Z
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.
Emil Jeřábek
CC BY-SA 4.0
2022-07-16T09:14:32.397Z
If this is a previously studied problem, please give a reference to a comprehensible definition.
Emil Jeřábek
CC BY-SA 4.0
2022-07-16T12:19:05.663Z
@ 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
CC BY-SA 4.0
2022-07-16T14:48:12.177Z
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.
Emil Jeřábek
CC BY-SA 4.0
2022-07-16T17:49:49.363Z
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
<ds.algorithms><co.combinatorics><permutations>
Decomposition of a permutation into increasing subsequences
Vk1
# Decomposition of a permutation into increasing subsequences

(Asked by: username_0 on 2022-07-13)

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.

**Tags:** ds.algorithms, co.combinatorics, permutations
> **Comments:**
> **username_1**: 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.  
> **username_1**: If this is a previously studied problem, please give a reference to a comprehensible definition.  
> **username_0**: @ 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.  
> **username_1**: 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.  
> **username_0**: 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.  

---

## 1 answers

### Answer by username_2 on 2022-07-16. Score: 6

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.

> **Comments:**
> **username_0**: Never been so happy to be wrong. Thank you Professor Peter Shor.  

---

