Descents, Quasi-Symmetric Functions, Robinson-Schensted for Posets, and the Chromatic Symmetric Function
Timothy Y. Chow
DOI: 10.1023/A:1018719315718
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.
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.Pages: 227–240
Keywords: (3 + 1)-free poset; chromatic polynomial
Full Text: PDF
References
1. F. Brenti, “Expansions of chromatic polynomials and log-concavity,” Trans. Amer. Math. Soc. 332 (1992), 729-756.
2. T. Chow, “The path-cycle symmetric function of a digraph,” Advances in Math. 118 (1996), 71-98.
3. F. Chung and R. Graham, “On the cover polynomial of a digraph,” J. Combin. Theory (Ser. B) 65 (1995), 273-290.
4. F.N. David and M.G. Kendall, “Tables of symmetric functions. I,” Biometrika 36 (1949), 431-449.
5. 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.
6. V. Gasharov, “Incomparability graphs of (3 + 1)-free posets are s-positive,” Discrete Math. 157 (1996), 193-197.
7. 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.
8. I.G. Macdonald, Symmetric Functions and Hall Polynomials, 2nd edition, Oxford University Press, Oxford, 1995.
9. A. Magid, “Enumeration of convex polyominoes: a generalization of the Robinson-Schensted correspondence and the dimer problem,” Ph.D. Thesis, Brandeis University, 1992.
10. B.E. Sagan, The Symmetric Group: Representations, Combinatorial Algorithms, and Symmetric Functions, Wadsworth & Brooks/Cole, Pacific Grove, CA, 1991.
11. R.P. Stanley, “Acyclic orientations of graphs,” Discrete Math. 5 (1973), 171-178. CHOW
12. R.P. Stanley, “A symmetric function generalization of the chromatic polynomial of a graph,” Advances in Math. 111 (1995), 166-194.
13. R.P. Stanley, Enumerative Combinatorics, Vol. 1, Wadsworth & Brooks/Cole, Pacific Grove, CA, 1986.
14. R.P. Stanley, “Graph colorings and related symmetric functions: ideas and applications,” Discrete Math., 193 (1998), 267-286.
15. 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.
2. T. Chow, “The path-cycle symmetric function of a digraph,” Advances in Math. 118 (1996), 71-98.
3. F. Chung and R. Graham, “On the cover polynomial of a digraph,” J. Combin. Theory (Ser. B) 65 (1995), 273-290.
4. F.N. David and M.G. Kendall, “Tables of symmetric functions. I,” Biometrika 36 (1949), 431-449.
5. 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.
6. V. Gasharov, “Incomparability graphs of (3 + 1)-free posets are s-positive,” Discrete Math. 157 (1996), 193-197.
7. 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.
8. I.G. Macdonald, Symmetric Functions and Hall Polynomials, 2nd edition, Oxford University Press, Oxford, 1995.
9. A. Magid, “Enumeration of convex polyominoes: a generalization of the Robinson-Schensted correspondence and the dimer problem,” Ph.D. Thesis, Brandeis University, 1992.
10. B.E. Sagan, The Symmetric Group: Representations, Combinatorial Algorithms, and Symmetric Functions, Wadsworth & Brooks/Cole, Pacific Grove, CA, 1991.
11. R.P. Stanley, “Acyclic orientations of graphs,” Discrete Math. 5 (1973), 171-178. CHOW
12. R.P. Stanley, “A symmetric function generalization of the chromatic polynomial of a graph,” Advances in Math. 111 (1995), 166-194.
13. R.P. Stanley, Enumerative Combinatorics, Vol. 1, Wadsworth & Brooks/Cole, Pacific Grove, CA, 1986.
14. R.P. Stanley, “Graph colorings and related symmetric functions: ideas and applications,” Discrete Math., 193 (1998), 267-286.
15. 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.