1
$\begingroup$

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'<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.

$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$ Jul 16, 2022 at 8:22
  • $\begingroup$ If this is a previously studied problem, please give a reference to a comprehensible definition. $\endgroup$ Jul 16, 2022 at 9:14
  • $\begingroup$ @ 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. $\endgroup$
    – Vk1
    Jul 16, 2022 at 12:19
  • $\begingroup$ 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. $\endgroup$ Jul 16, 2022 at 14:48
  • $\begingroup$ 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. $\endgroup$
    – Vk1
    Jul 16, 2022 at 17:49

1 Answer 1

6
+50
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.