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

The author presents a new version of the expansion of Stanley's chromatic symmetric function [\textit{R. P. Stanley}, Discrete Math. 5, 171-178 (1973; Zbl 0258.05113)] in terms of Gessel's fundamental quasi-symmetric functions [\textit{I. M. Gessel}, Combinatorics and algebra, Proc. Conf., Boulder/Colo. 1983, Contemp. Math. 34, 289-301 (1984; Zbl 0562.05007)]. He shows that, although innocent-looking, this expansion has a lot of applications, some of them rather surprising. The author establishes that the \(G\)-descent expansion of the chromatic polynomial [\textit{F. R. K. Chung} and \textit{R. L. Graham}, J. Comb. Theory, Ser. B 65, No. 2, 273-290 (1995; Zbl 0839.05045)] and an important special case of his expansion of the path-cycle symmetric function [\textit{T. Y. Chow}, Adv. Math. 118, No. 1, 71-98, Art. No. 0018 (1996; Zbl 0847.05098)] are direct consequences of the new version of the Stanley theorem. Then the author investigates the application of Stanley's expansion for Robinson-Schensted algorithms for (\textbf{3} + \textbf{1})-free posets. By recent algebraic arguments of \textit{V. Gasharov} [Discrete Math. 157, No. 1-3, 193-197 (1996; Zbl 0856.05042)] there ought to exist such an algorithm which generalizes the usual Robinson-Schensted algorithm, but no such general algorithm is currently known. The author shows that the algorithm should respect descents, i.e. the best known partial result [\textit{T. S. Sundquist, D. G. Wagner} and \textit{J. West}, J. Comb. Theory, Ser. A 79, No. 1, 36-52, Art. No. TA972769 (1997; Zbl 0882.05113)] should be modified even for the smaller class of ``beast-free'' (\textbf{3} + \textbf{1})-free posets. Finally the author investigates connections with the new symmetric function basis introduced in his paper cited above, providing evidences that his basis is a worthy object of study.