Chromatic symmetric functions and change of basis

Sagan, Bruce E.; Tom, Foster

doi:10.5802/alco.468

¹Department of Mathematics, Michigan State University, East Lansing, MI 48824
²Department of Mathematics, Dartmouth College, Hanover, NH 03755

Algebraic Combinatorics, Volume 9 (2026) no. 1, pp. 307-325

Abstract

We prove necessary conditions for certain elementary symmetric functions, $e_\lambda $, to appear with nonzero coefficient in Stanley’s chromatic symmetric function as well as in the generalization considered by Shareshian and Wachs. We do this by first considering the expansion in the monomial or Schur basis and then performing a basis change. Using the former, we make a connection with two fundamental graph theory invariants, the independence and clique numbers. This allows us to prove nonnegativity of three-column coefficients for all natural unit interval graphs, giving more insight into the Stanley–Stembridge Conjecture, recently proven by Hikita, and the Shareshian–Wachs Conjecture. The Schur basis permits us to give a new interpretation of the coefficient of $e_n$ in terms of tableaux. We are also able to give an explicit formula for that coefficient.

Received: 2024-07-08
Revised: 2025-08-16
Accepted: 2025-11-09
Published online: 2026-03-03

DOI: 10.5802/alco.468

Classification: 05E05, 05C15, 05C31, 05E10
Keywords: chromatic quasisymmetric function, elementary symmetric function, monomial symmetric function, natural unit interval graph, proper colouring, Shareshian–Wachs conjecture, Stanley–Stembridge conjecture

Author's affiliations:

Sagan, Bruce E. ¹ ; Tom, Foster ²

¹ Department of Mathematics, Michigan State University, East Lansing, MI 48824
² Department of Mathematics, Dartmouth College, Hanover, NH 03755

License:

CC-BY 4.0

Copyrights: The authors retain unrestricted copyrights and publishing rights

@article{ALCO_2026__9_1_307_0,
     author = {Sagan, Bruce E. and Tom, Foster},
     title = {Chromatic symmetric functions and change of basis},
     journal = {Algebraic Combinatorics},
     pages = {307--325},
     year = {2026},
     publisher = {The Combinatorics Consortium},
     volume = {9},
     number = {1},
     doi = {10.5802/alco.468},
     language = {en},
     url = {https://alco.centre-mersenne.org/articles/10.5802/alco.468/}
}

TY  - JOUR
AU  - Sagan, Bruce E.
AU  - Tom, Foster
TI  - Chromatic symmetric functions and change of basis
JO  - Algebraic Combinatorics
PY  - 2026
SP  - 307
EP  - 325
VL  - 9
IS  - 1
PB  - The Combinatorics Consortium
UR  - https://alco.centre-mersenne.org/articles/10.5802/alco.468/
DO  - 10.5802/alco.468
LA  - en
ID  - ALCO_2026__9_1_307_0
ER  -

%0 Journal Article
%A Sagan, Bruce E.
%A Tom, Foster
%T Chromatic symmetric functions and change of basis
%J Algebraic Combinatorics
%D 2026
%P 307-325
%V 9
%N 1
%I The Combinatorics Consortium
%U https://alco.centre-mersenne.org/articles/10.5802/alco.468/
%R 10.5802/alco.468
%G en
%F ALCO_2026__9_1_307_0

Sagan, Bruce E.; Tom, Foster. Chromatic symmetric functions and change of basis. Algebraic Combinatorics, Volume 9 (2026) no. 1, pp. 307-325. doi: 10.5802/alco.468

References
Cited by

[1] Abreu, A.; Nigro, A. Splitting the cohomology of Hessenberg varieties and $e$ -positivity of chromatic symmetric functions, 2023 | arXiv | Zbl

[2] Aliste-Prieto, José; de Mier, Anna; Orellana, Rosa; Zamora, José Marked graphs and the chromatic symmetric function, SIAM J. Discrete Math., Volume 37 (2023) no. 3, pp. 1881-1919 | DOI | MR | Zbl

[3] Cho, Soojin; Hong, Jaehyun Positivity of chromatic symmetric functions associated with Hessenberg functions of bounce number 3, Electron. J. Combin., Volume 29 (2022) no. 2, Paper no. 2.19, 37 pages | DOI | MR | Zbl

[4] Cho, Soojin; Huh, Jisun On $e$ -positivity and $e$ -unimodality of chromatic quasi-symmetric functions, SIAM J. Discrete Math., Volume 33 (2019) no. 4, pp. 2286-2315 | DOI | MR | Zbl

[5] Cho, Soojin; van Willigenburg, Stephanie Chromatic bases for symmetric functions, Electron. J. Combin., Volume 23 (2016) no. 1, Paper no. 1.15, 7 pages | DOI | MR | Zbl

[6] Clearman, Samuel; Hyatt, Matthew; Shelton, Brittany; Skandera, Mark Evaluations of Hecke algebra traces at Kazhdan-Lusztig basis elements, Electron. J. Combin., Volume 23 (2016) no. 2, Paper no. 2.7, 56 pages | DOI | MR | Zbl

[7] Dahlberg, S. Triangular ladders $P_{d, 2}$ are $e$ -positive, 2018 | arXiv | Zbl

[8] Gasharov, Vesselin Incomparability graphs of $(3 + 1)$ -free posets are $s$ -positive, Proceedings of the 6th Conference on Formal Power Series and Algebraic Combinatorics (New Brunswick, NJ, 1994) (157) (1996) no. 1-3, pp. 193-197 | DOI | MR | Zbl

[9] Gebhard, David D.; Sagan, Bruce E. A chromatic symmetric function in noncommuting variables, J. Algebraic Combin., Volume 13 (2001) no. 3, pp. 227-255 | DOI | MR | Zbl

[10] Greene, Curtis An extension of Schensted’s theorem, Advances in Math., Volume 14 (1974), pp. 254-265 | DOI | MR | Zbl

[11] Greene, Curtis; Zaslavsky, Thomas On the interpretation of Whitney numbers through arrangements of hyperplanes, zonotopes, non-Radon partitions, and orientations of graphs, Trans. Amer. Math. Soc., Volume 280 (1983) no. 1, pp. 97-126 | DOI | MR | Zbl

[12] Guay-Paquet, M. A modular law for the chromatic symmetric functions of $(3 + 1)$ -free posets, 2013 | arXiv | Zbl

[13] Harada, Megumi; Precup, Martha E. The cohomology of abelian Hessenberg varieties and the Stanley-Stembridge conjecture, Algebr. Comb., Volume 2 (2019) no. 6, pp. 1059-1108 | DOI | MR | Numdam | Zbl

[14] Hikita, T. A proof of the Stanley-Stembridge conjecture, 2024 | arXiv

[15] Hwang, Byung-Hak Chromatic quasisymmetric functions and noncommutative $P$ -symmetric functions, Trans. Amer. Math. Soc., Volume 377 (2024) no. 4, pp. 2855-2896 | DOI | MR | Zbl

[16] Rok, A.; Szenes, A. Eschers and Stanley’s chromatic $e$ -positivity conjecture in length-2, 2023 | arXiv | Zbl

[17] Sagan, Bruce E. The symmetric group: Representations, combinatorial algorithms, and symmetric functions, The Wadsworth & Brooks/Cole Mathematics Series, Wadsworth & Brooks/Cole Advanced Books & Software, Pacific Grove, CA, 1991, xviii+197 pages | MR | Zbl

[18] Schensted, C. Longest increasing and decreasing subsequences, Canadian J. Math., Volume 13 (1961), pp. 179-191 | DOI | MR | Zbl

[19] Shareshian, John; Wachs, Michelle L. Chromatic quasisymmetric functions, Adv. Math., Volume 295 (2016), pp. 497-551 | DOI | MR | Zbl

[20] Stanley, Richard P. A symmetric function generalization of the chromatic polynomial of a graph, Adv. Math., Volume 111 (1995) no. 1, pp. 166-194 | DOI | MR | Zbl

[22] Stanley, Richard P.; Stembridge, John R. On immanants of Jacobi-Trudi matrices and permutations with restricted position, J. Combin. Theory Ser. A, Volume 62 (1993) no. 2, pp. 261-279 | DOI | MR | Zbl

[23] Tom, Foster A signed $e$ -expansion of the chromatic quasisymmetric function, Comb. Theory, Volume 5 (2025) no. 2, Paper no. 11, 36 pages | MR | Zbl

Cited by Sources: