For any permutation $\sigma\in S_k$ and any $i\in\left\lbrace 1,2,...,k\right\rbrace$, I will denote $\sigma\left(i\right)$ by $\sigma_i$.

For any word $w$, I will denote by $\mathrm{st}w$ the standardization of the word $w$ (that is, the unique permutation $\sigma \in S_k$, where $k$ is the length of $w$, to satisfy the following property: for any $i < j$, we have $\sigma_i \leq \sigma_j$ if and only if the $i$-th letter of $w$ is $\leq$ to the $j$-th letter of $w$).

Let $n$ be a nonnegative integer. Let $\sigma$ and $\tau$ be two Knuth-equivalent permutations in $S_n$ (that is, two permutations in $S_n$ whose insertion tableaux under the Robinson-Schensted-Knuth correspondence are equal). Let $k\in\left\lbrace 0,1,...,n\right\rbrace$. Assume that

$\mathrm{st}\left(\sigma_1\sigma_2...\sigma_k\right) = \mathrm{st}\left(\tau_1\tau_2...\tau_k\right)$ and $\mathrm{st}\left(\sigma_{k+1}\sigma_{k+2}...\sigma_n\right) = \mathrm{st}\left(\tau_{k+1}\tau_{k+2}...\tau_n\right)$.

Do we then necessarily have $\sigma = \tau$ ?

I fear I have no actual context to offer for this conjecture. I found it when trying to figure out why certain buggy code I had written did not create any wrong results (I tried to compute the product in one of the Poirier-Reutenauer Hopf algebras, but did not take into account the possibility that it might not be multiplicity-free; the above conjecture states that it actually is multiplicity-free). It is tested for all $n\leq 10$, and can easily be proven if $k\leq 1$ or $k\geq n-1$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.