20
$\begingroup$

The Robinson-Schensted correspondence is a bijection between elements of the symmetric group $S_n$ and pairs of standard tableaux of the same shape. The symmetric group is partially ordered by the Bruhat order, so this bijection induces a partial ordering "$\leq$"on the set of pairs of standard tableaux. Is there a natural "tableaux-theoretic" description of $\leq$? That is, can we give a necessary and sufficient condition for $(S,T)\leq (S',T')$ intrinsic to the set of pairs of tableaux?

(this was posted at mse a few weeks ago to no response)

Added later: Each involution in $S_n$ is mapped to a pair $(P,P)$, so Bruhat order on involutions induces an order on standard tableaux. Characterising this order is listed as an `unsolved problem' in Björner and Brenti's Combinatorics of Coxeter Groups.

Improve this question
$\endgroup$
  • 1
    $\begingroup$ You could also ask the same question about weak order -- which could conceivably be somewhat easier to analyze and perhaps a good warm-up for Bruhat order. $\endgroup$ – Patricia Hersh Jul 15 '12 at 1:46
  • $\begingroup$ I have seen the weak order studied on the insertion tableau, see "Reiner, Taskin - The weak and Kazhdan-Lusztig orders on standard Yound tableaux" and references therein (for example Anna Melnikov's paper mentioned by Jim below as well). $\endgroup$ – Christian Stump Jul 15 '12 at 5:56
9
$\begingroup$

The question is natural but looks difficult to approach strictly within the combinatorial definitions. Maybe it's helpful here to suggest a broader geometric framework, which applies more generally to reductive algebraic groups but involves here a general linear group having the symmetric group $S_n$ as Weyl group. Recall that the "Bruhat order" was defined by Chevalley in the more general setting as the order on Bruhat cells in the flag variety given by inclusion of one cell in the closure of another. These cells are naturally labelled by elements of $S_n$.

On the other hand, the associated geometry of the flag variety and its cotangent bundle (work of Springer, Steinberg, Spaltenstein) leads to Springer fibers with equidimensional components. For the general linear case, these Springer fibers in the flag variety correspond to partitions (Jordan forms of unipotent elements). In this set-up, pairs of typical flags in components of a Springer fiber relate naturally to pairs of standard tableaux of the shape determined by an element of $S_n$, correlating with the Robinson-Schensted correspondence. This is brought out by Steinberg in a short paper here. The Bruhat order is lurking in all of this machinery, but the connection with Robinson-Schensted isn't made explicit enough.

A further related 2005 paper by Anna Melnikov appears here, treating the combinatorics of orbital varieties (but only in a very special case).

Improve this answer
$\endgroup$
  • $\begingroup$ I'd feared that the geometry would appear here: perhaps it is the only way. Thanks for the Melnikov paper, there is a lot that is relevant in there. $\endgroup$ – M T Jul 17 '12 at 8:34

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.