Descents, quasi-symmetric functions, Robinson-Schensted for posets, and the chromatic symmetric function

Chow, Timothy Y.

Journal of Algebraic Combinatorics, Tome 10 (1999) no. 3, pp. 227-240.

Résumé

Summary: We investigate an apparent hodgepodge of topics: a Robinson-Schensted algorithm for (3 + 1)-free posets, Chung and Graham's G-descent expansion of the chromatic polynomial, a quasi-symmetric expansion of the path-cycle symmetric function, and an expansion of Stanley's chromatic symmetric function X $_{ G }$ in terms of a new symmetric function basis. We show how the theory of P-partitions (in particular, Stanley's quasi-symmetric function expansion of the chromatic symmetric function X $_{ G }$) unifies them all, subsuming two old results and implying two new ones. Perhaps our most interesting result relates to the still-open problem of finding a Robinson-Schensted algorithm for (3 + 1)-free posets. (Magid has announced a solution but it appears to be incorrect.) We show that such an algorithm ought to $ldquo$respect descents $rdquo$, and that the best partial algorithm so far-due to Sundquist, Wagner, and West-respects descents if it avoids a certain induced subposet.

Détail

Keywords: (3 + 1)-free poset, chromatic polynomial