A Chromatic Symmetric Function in Noncommuting Variables
David D. Gebhard1
and Bruce E. Sagan2
1Wisconsin Lutheran College Department of Mathematics 8800 W. Bluemont Rd. Milwaukee WI 53226 USA
2Michigan State University Department of Mathematics East Lansing MI 48824-1027 USA
2Michigan State University Department of Mathematics East Lansing MI 48824-1027 USA
DOI: 10.1023/A:1011258714032
Abstract
Stanley ( Advances in Math. 111, 1995, 166-194) associated with a graph G a symmetric function X G which reduces to G's chromatic polynomial X G ( n ) {\mathcal{X}_G \left( n \right)} under a certain specialization of variables. He then proved various theorems generalizing results about X G ( n ) {\mathcal{X}_G \left( n \right)} , as well as new ones that cannot be interpreted on the level of the chromatic polynomial. Unfortunately, X G does not satisfy a Deletion-Contraction Law which makes it difficult to apply the useful technique of induction. We introduce a symmetric function Y G in noncommuting variables which does have such a law and specializes to X G when the variables are allowed to commute. This permits us to further generalize some of Stanley's theorems and prove them in a uniform and straightforward manner. Furthermore, we make some progress on the ( 3 + 1)-free Conjecture of Stanley and Stembridge ( J. Combin Theory ( A) J. 62, 1993, 261-279).
Pages: 227–255
Keywords: chromatic polynomial; deletion-contraction; graph; symmetric function in noncommuting variables
Full Text: PDF
References
1. A. Blass and B. Sagan, “Bijective proofs of two broken circuit theorems,” J. Graph Theory 10 (1986), 15-21.
2. T. Chow, personal communication.
3. 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.
4. V. Gasharov, “Incomparability graphs of (3 + 1)-free posets are s-positive,” Discrete Math. 157 (1996), 193- 197.
5. D. Gebhard, “Noncommutative symmetric functions and the chromatic polynomial,” Conference Proceedings at the 7th International Conference on Formal Power Series and Algebraic Combinatorics, Université de Marne-la-Vallée, 1995.
6. D. Gebhard and B. Sagan, “Sinks in acyclic orientations of graphs,” J. Combin. Theory (B) 80 (2000), 130-146.
7. I.M. Gelfand, D. Krob, A. Lascoux, B. Leclerc, V. Retakh, and J.-I. Thibon, “Noncommutative symmetric functions,” Advances in Math. 112 (1995), 218-348.
8. C. Greene and T. Zaslavsky, “On the interpretation of Whitney numbers through arrangements of hyperplanes, zonotopes, non-radon partitions, and orientations of graphs,” Trans. Amer. Math. Soc. 280 (1983), 97-126.
9. F. Harary and E. Palmer, “The reconstruction of a tree from its maximal subtrees,” Canad. J. Math. 18 (1966), 803-810.
10. R.P. Stanley, “Acyclic orientations of graphs,” Discrete Math. 5 (1973), 171-178.
11. R.P. Stanley, “A symmetric function generalization of the chromatic polynomial of a graph,” Advances in Math. 111 (1995), 166-194.
12. R.P. Stanley, “Graph colorings and related symmetric functions: Ideas and applications: A description of results, interesting applications, & notable open problems,” Selected papers in honor of Adriano Jarsia (Taormina, 1994) Discrete Math. 193 (1998), 267-286.
13. R.P. Stanley and J. Stembridge, “On immanants of Jacobi-Trudi matrices and permutations with restricted position,” J. Combin. Theory (A) 62 (1993), 261-279.
14. S.D. Noble and D.J.A. Welsh, “A weighted graph polynomial from chromatic invariants of knots,” Symposium `a la Mémoire de Fran\?cois Jaeger (Grenoble, 1998) Annales l'Institut Fourier 49 (1999), 1057-1087.
2. T. Chow, personal communication.
3. 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.
4. V. Gasharov, “Incomparability graphs of (3 + 1)-free posets are s-positive,” Discrete Math. 157 (1996), 193- 197.
5. D. Gebhard, “Noncommutative symmetric functions and the chromatic polynomial,” Conference Proceedings at the 7th International Conference on Formal Power Series and Algebraic Combinatorics, Université de Marne-la-Vallée, 1995.
6. D. Gebhard and B. Sagan, “Sinks in acyclic orientations of graphs,” J. Combin. Theory (B) 80 (2000), 130-146.
7. I.M. Gelfand, D. Krob, A. Lascoux, B. Leclerc, V. Retakh, and J.-I. Thibon, “Noncommutative symmetric functions,” Advances in Math. 112 (1995), 218-348.
8. C. Greene and T. Zaslavsky, “On the interpretation of Whitney numbers through arrangements of hyperplanes, zonotopes, non-radon partitions, and orientations of graphs,” Trans. Amer. Math. Soc. 280 (1983), 97-126.
9. F. Harary and E. Palmer, “The reconstruction of a tree from its maximal subtrees,” Canad. J. Math. 18 (1966), 803-810.
10. R.P. Stanley, “Acyclic orientations of graphs,” Discrete Math. 5 (1973), 171-178.
11. R.P. Stanley, “A symmetric function generalization of the chromatic polynomial of a graph,” Advances in Math. 111 (1995), 166-194.
12. R.P. Stanley, “Graph colorings and related symmetric functions: Ideas and applications: A description of results, interesting applications, & notable open problems,” Selected papers in honor of Adriano Jarsia (Taormina, 1994) Discrete Math. 193 (1998), 267-286.
13. R.P. Stanley and J. Stembridge, “On immanants of Jacobi-Trudi matrices and permutations with restricted position,” J. Combin. Theory (A) 62 (1993), 261-279.
14. S.D. Noble and D.J.A. Welsh, “A weighted graph polynomial from chromatic invariants of knots,” Symposium `a la Mémoire de Fran\?cois Jaeger (Grenoble, 1998) Annales l'Institut Fourier 49 (1999), 1057-1087.