15
$\begingroup$

The Robinson-Schensted correspondence is a bijection between elements of the symmetric group and ordered pairs of standard tableaux of the same shape.

Some simple operations on tableaux correspond to simple operations on the group: switching the tableaux corresponds to inverse on the group.

What about taking the transpose of the tableaux? Does that correspond to something easily described on permutations?

In order to rule out easy guesses, let me describe this on $S_3$:

  • the identity switches with the involution 321.
  • the transpositions 213 and 132 switch.
  • the 3-cycles 312 and 231 switch.

In general, this operation preserves being order $\leq 2$ (since this is equivalent to the P- and Q-symbols being the same).

$\endgroup$
2
  • $\begingroup$ Have you tried enough cases to rule out simple guesses like "replace each i in the word representation by n+1-i"? $\endgroup$ Feb 7, 2010 at 18:40
  • $\begingroup$ My experience with these kinds of questions is that somehow the answer is in Enumerative Combinatorics, but maybe this time Stanley can't come to the rescue! $\endgroup$ Feb 7, 2010 at 18:45

3 Answers 3

10
$\begingroup$

When you conjugate diagrams and apply RSK or other Young tableau bijections, the answer is typically bad, with some rare exceptions. The right way to think of RSK is to think of row length being continuous while columns still integer (see e.g. my "Geometric proof of the hook-length formula" paper and refs therein).

An exception: there is a "hidden symmetry" for LR-coefficients when you conjugate all three diagrams - see Hanlon-Sundaram paper (1992). Once you know this bijection, there are natural connections to RSK as described in the long Pak-Vallejo paper and a followup by Azenhas-Conflitti-Mamede (search the web for a paper and a ppt presentation). Together, these do give a complete description of your involution, but making sense of it might require quite a bit of work.

$\endgroup$
10
$\begingroup$

It doesn't seem natural to the theory of RSK to transpose both tableaux. When we apply RSK to $a_n\cdots a_1$ then we get the pair $(P^t,\mathrm{evac}(Q)^t)$, where evac is Schutzenberger's evacuation operation. See for instance Enumerative Combinatorics, vol. 2, pp. 425--429. For more on evacuation, see https://doi.org/10.37236/75.

$\endgroup$
2
$\begingroup$

Edit: This doesn't answer the question; see comments.

Knuth, TAoCP3, p. 76, exercise 5 in section 5.1.4:

Let $P$ be the tableau corresponding to the permutation $a_1a_2...a_n$; use exercise 4 to prove that $P^T$ is the tableau corresponding to $a_n...a_2a_1$.

$\endgroup$
5
  • $\begingroup$ I'll just note, this operation transposes the P-symbol (this is easy to see from jeu de taquin) but it doesn't transpose the Q-symbols, since it doesn't preserve being an involution. $\endgroup$
    – Ben Webster
    Feb 7, 2010 at 19:10
  • $\begingroup$ Ah, sorry. At least it gives a negative answer: the involution is not in Knuth TAoCP, 5.1. $\endgroup$ Feb 7, 2010 at 19:15
  • $\begingroup$ So what does transposing the Q-symbol correspond to? (I have to confess I can't do RSK quickly enough to just experiment for myself.) $\endgroup$ Feb 7, 2010 at 20:33
  • $\begingroup$ Can't we do this, invert, do this again, invert, to transpose both tableaux? $\endgroup$ Feb 7, 2010 at 22:33
  • 2
    $\begingroup$ I think that when Ben said "it doesn't transpose the Q-symbols", he didn't mean "it leaves the Q-symbols fixed". See Richard's reply. $\endgroup$ Feb 8, 2010 at 0:35

Your Answer

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

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