Both Kazhdan-Lusztig and Steinberg have defined pairs of preorders on $S_n$. Kazhdan and Lusztig's preorders come from their basis:

We write $x\leq_L y$ if any left ideal spanned by K-L basis vectors which contains $C_y$ also contains $C_x$. Similarly for $x\leq_R y$ and right ideals.

Note that $x\leq_L y$ if and only if $x^{-1}\leq_R y^{-1}$, so all the information is in one of these preorders.

Now, we can define a geometric preorder satisfying similar properties, following Steinberg. Let $\mathfrak{n}$ be the usual strictly upper-triangular matrices in $\mathfrak{sl}_n$ and let $\mathfrak{n}\cap\mathfrak{n}^w$ be its intersection with itself conjugated by $w$. We let $x\leq_l y$ if $B\cdot (\mathfrak{n}\cap\mathfrak{n}^y)\subset B\cdot (\mathfrak{n}\cap\mathfrak{n}^x)$, and $x\leq_r y$ if $x^{-1}\leq_ly^{-1}$.

Do the preorders $\leq_L$ and $\leq_l$ coincide?

It's a theorem (look, for example in Appendix B of Borho and Brylinski, Differential... III) that the equivalence relations induced by them (the left cells) do; they're both distinguished by their $Q$-symbol under Robinson-Schensted.

Do these preorders have a nice description in terms of Robinson-Schensted?

**EDIT:** After speaking with various people, I believe this is an open question, and quite an interesting one in my opinion.

Remarques sur certaines relations d'equivalence dans les groupes de Weyl. In type A, where all nilpotent orbits are special, it seems plausible that the pre-orders and not just the equivalence relations should coincide. An interesting question apparently not addressed in Spaltenstein's later Springer LN volume. – Jim Humphreys Jan 27 '11 at 21:20