Robinson-Schensted algorithm for a class of partial orders

摘要

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}. (C) 1997 Academic Press.