Abstract
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 “respect descents”, and that the best partial algorithm so far—due to Sundquist, Wagner, and West—respects descents if it avoids a certain induced subposet.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
F. Brenti, “Expansions of chromatic polynomials and log-concavity,” Trans. Amer. Math. Soc. 332 (1992), 729–756.
T. Chow, “The path-cycle symmetric function of a digraph,” Advances in Math. 118 (1996), 71–98.
F. Chung and R. Graham, “On the cover polynomial of a digraph,” J. Combin. Theory (Ser. B) 65 (1995), 273–290.
F.N. David and M.G. Kendall, “Tables of symmetric functions. I,” Biometrika 36 (1949), 431–449.
P. Doubilet, “On the foundations of combinatorial theory. VII: Symmetric functions through the theory of distribution and occupancy,” Studies in Applied Math. 51 (1972), 377–396.
V. Gasharov, “Incomparability graphs of (3 + 1)-free posets are s-positive,” Discrete Math. 157 (1996), 193–197.
I.M. Gessel, “Multipartite P-partitions and inner products of skew Schur functions,” in Combinatorics and Algebra, C. Greene (Ed.), Contemporary Mathematics Series, Vol. 34, Amer. Math. Soc., Providence, R.I., 1984, pp. 289–301.
I.G. Macdonald, Symmetric Functions and Hall Polynomials, 2nd edition, Oxford University Press, Oxford, 1995.
A. Magid, “Enumeration of convex polyominoes: a generalization of the Robinson-Schensted correspondence and the dimer problem,” Ph.D. Thesis, Brandeis University, 1992.
B.E. Sagan, The Symmetric Group: Representations, Combinatorial Algorithms, and Symmetric Functions, Wadsworth & Brooks/Cole, Pacific Grove, CA, 1991.
R.P. Stanley, “Acyclic orientations of graphs,” Discrete Math. 5 (1973), 171–178.
R.P. Stanley, “A symmetric function generalization of the chromatic polynomial of a graph,” Advances in Math. 111 (1995), 166–194.
R.P. Stanley, Enumerative Combinatorics, Vol. 1, Wadsworth & Brooks/Cole, Pacific Grove, CA, 1986.
R.P. Stanley, “Graph colorings and related symmetric functions: ideas and applications,” Discrete Math., 193 (1998), 267–286.
T.S. Sundquist, D.G. Wagner, and J. West, “A Robinson-Schensted algorithm for a class of partial orders,” J. Combin. Theory Ser. A 79 (1997), 36–52.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Chow, T.Y. Descents, Quasi-Symmetric Functions, Robinson-Schensted for Posets, and the Chromatic Symmetric Function. Journal of Algebraic Combinatorics 10, 227–240 (1999). https://doi.org/10.1023/A:1018719315718
Issue Date:
DOI: https://doi.org/10.1023/A:1018719315718