3
$\begingroup$

In the title, $LIS$ stands for the length of longest increasing subsequence and Greek letters stand for permutations from symmetric group $S_n$.

Considering some cases such as $\pi^{-1}=\sigma=involution$, then $LIS(\sigma\pi^{-1})=LIS(\pi^2)=LIS(i.d.)=k$. Or in more extreme case where $\pi=\sigma =\overline{n(n-1)...321}$, we still have a lower bound of order $n$. It feels like if two of them are too small, then the third one should be well compensated so that the summation is somewhat lower bounded.

Roughly a more rigorous explanation for above situation is that from Young tableaux view, we have for any permutation $LIS(\sigma)\times LDS(\sigma)>n$, where $LDS$ stands for the length of longest decreasing subsequence. So if $LIS(\sigma)$ and $LIS(\pi)$ are both small then $LDS(\sigma)$ and $LDS(\pi)$ are both large so that there are enough overlapping between longest decreasing subseqences of $\sigma$ and $\pi$ and hence the operation $\sigma\pi^{-1}$ makes the overlapped part get mapped into an increasing subseqence. Then our $LIS(\sigma\pi^{-1})$ is large enough.

By the symmetry between $LIS$ and $LDS$, I would guess the proposed lower bound is of order same as $\sqrt{n}$.

If the proposed inequality is disproved, will there be a function $f(LIS(\pi),LIS(\sigma),LIS(\sigma\pi^{-1}))$ such that it is increasing w.r.t. the three variables and still lower bounded which could describe the balance to some extent?

Any input is welcomed and thanks in advance!

$\endgroup$
1
  • $\begingroup$ There is a tight lower bound for the triple product: $$LCS(\pi_1,\pi_2)LCS(\pi_2,\pi_3)LCS(\pi_3,\pi_1)\ge n$$ $\endgroup$ Jan 15, 2017 at 21:19

0

Your Answer

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