A Robinson–Schensted Algorithm for a Class of Partial Orders

✍ Scribed by Thomas S. Sundquist; David G. Wagner; Julian West

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 378 KB
• Volume: 79
• Category: Article
• ISSN: 0097-3165
• DOI: 10.1006/jcta.1997.2769

✦ Synopsis

Let P be a finite partial order which does not contain an induced subposet isomorphic with 3+1, and let G be the incomparability graph of P. Gasharov has shown that the chromatic symmetric function X G has nonnegative coefficients when expanded in terms of Schur functions; his proof uses the dual Jacobi Trudi identity and a sign-reversing involution to interpret these coefficients as numbers of P-tableau. This suggests the possibility of a direct bijective proof of this result, generalizing the Robinson Schensted correspondence. We provide such an algorithm here under the additional hypothesis that P does not contain an induced subposet isomorphic with [x>ay].
1997 Academic Press 0. INTRODUCTION An apt subtitle for this paper would be ``a long complicated argument for a special case of a more general theorem which has a short elegant proof.'' As such, we must not only present our result clearly, but also explain why article no. TA972769 36 0097-3165Â97 25.00