ALGEBRAIC COMBINATORICS

no. 3
Quasisymmetric functions distinguishing trees
Aval, Jean-Christophe1; Djenabou, Karimatou2; McNamara, Peter R. W.3
1 LaBRI, CNRS, Université de Bordeaux 351 cours de la Libération 33405 Talence France
2 African Institute for Mathematical Sciences 6 Melrose Road Muizenberg 7945 South Africa
3 Department of Mathematics, Bucknell University Lewisburg, PA 17837 USA
Algebraic Combinatorics, Volume 6 (2023) no. 3, pp. 595-614.

A famous conjecture of Stanley states that his chromatic symmetric function distinguishes trees. As a quasisymmetric analogue, we conjecture that the chromatic quasisymmetric function of Shareshian and Wachs and of Ellzey distinguishes directed trees. This latter conjecture would be implied by an affirmative answer to a question of Hasebe and Tsujie about the P-partition enumerator distinguishing posets whose Hasse diagrams are trees. They proved the case of rooted trees and our results include a generalization of their result.

Received:
Revised:
Accepted:
Published online:
DOI: 10.5802/alco.273
Classification: 05E05, 06A07, 06A11, 05C05, 05C20
Keywords: chromatic, quasisymmetric function, digraph, poset, P-partition, rooted tree
Aval, Jean-Christophe 1; Djenabou, Karimatou 2; McNamara, Peter R. W. 3

1 LaBRI, CNRS, Université de Bordeaux 351 cours de la Libération 33405 Talence France
2 African Institute for Mathematical Sciences 6 Melrose Road Muizenberg 7945 South Africa
3 Department of Mathematics, Bucknell University Lewisburg, PA 17837 USA
License: CC-BY 4.0
Copyrights: The authors retain unrestricted copyrights and publishing rights 
@article{ALCO_2023__6_3_595_0,
     author = {Aval, Jean-Christophe and Djenabou, Karimatou and McNamara, Peter R. W.},
     title = {Quasisymmetric functions distinguishing trees},
     journal = {Algebraic Combinatorics},
     pages = {595--614},
     publisher = {The Combinatorics Consortium},
     volume = {6},
     number = {3},
     year = {2023},
     doi = {10.5802/alco.273},
     language = {en},
     url = {https://alco.centre-mersenne.org/articles/10.5802/alco.273/}
}
TY  - JOUR
AU  - Aval, Jean-Christophe
AU  - Djenabou, Karimatou
AU  - McNamara, Peter R. W.
TI  - Quasisymmetric functions distinguishing trees
JO  - Algebraic Combinatorics
PY  - 2023
SP  - 595
EP  - 614
VL  - 6
IS  - 3
PB  - The Combinatorics Consortium
UR  - https://alco.centre-mersenne.org/articles/10.5802/alco.273/
DO  - 10.5802/alco.273
LA  - en
ID  - ALCO_2023__6_3_595_0
ER  - 
%0 Journal Article
%A Aval, Jean-Christophe
%A Djenabou, Karimatou
%A McNamara, Peter R. W.
%T Quasisymmetric functions distinguishing trees
%J Algebraic Combinatorics
%D 2023
%P 595-614
%V 6
%N 3
%I The Combinatorics Consortium
%U https://alco.centre-mersenne.org/articles/10.5802/alco.273/
%R 10.5802/alco.273
%G en
%F ALCO_2023__6_3_595_0
Aval, Jean-Christophe; Djenabou, Karimatou; McNamara, Peter R. W. Quasisymmetric functions distinguishing trees. Algebraic Combinatorics, Volume 6 (2023) no. 3, pp. 595-614. doi : 10.5802/alco.273. https://alco.centre-mersenne.org/articles/10.5802/alco.273/

[1] Alexandersson, Per; Sulzgruber, Robin P-partitions and p-positivity, Int. Math. Res. Not. IMRN (2021) no. 14, pp. 10848-10907 | DOI | MR | Zbl

[2] Aliste-Prieto, José; de Mier, Anna; Zamora, José On trees with the same restricted U-polynomial and the Prouhet-Tarry-Escott problem, Discrete Math., Volume 340 (2017) no. 6, pp. 1435-1441 | DOI | MR | Zbl

[3] Aliste-Prieto, José; de Mier, Anna; Zamora, José On the smallest trees with the same restricted U-polynomial and the rooted U-polynomial, Discrete Math., Volume 344 (2021) no. 3, p. 112255 | DOI | MR | Zbl

[4] Aliste-Prieto, José; Zamora, José Proper caterpillars are distinguished by their chromatic symmetric function, Discrete Math., Volume 315 (2014), pp. 158-164 | DOI | MR | Zbl

[5] Ballantine, Cristina; Daugherty, Zajj; Hicks, Angela; Mason, Sarah; Niese, Elizabeth On quasisymmetric power sums, J. Combin. Theory Ser. A, Volume 175 (2020), p. 105273, 37 | DOI | MR | Zbl

[6] Billera, Louis J.; Thomas, Hugh; van Willigenburg, Stephanie Decomposable compositions, symmetric quasisymmetric functions and equality of ribbon Schur functions, Adv. Math., Volume 204 (2006) no. 4, pp. 204-240 | DOI | MR | Zbl

[7] Ellzey, Brittney Chromatic quasisymmetric functions of directed graphs, Sém. Lothar. Combin., Volume 78B (2017), p. Art. 74, 12 | MR | Zbl

[8] Ellzey, Brittney A directed graph generalization of chromatic quasisymmetric functions (2017+) | arXiv

[9] Ellzey, Brittney On the Chromatic Quasisymmetric Functions of Directed Graphs, ProQuest LLC, Ann Arbor, MI, 2018, 146 pages Thesis (Ph.D.)–University of Miami | MR

[10] Fougere, Joshua J. On symmetric chromatic polynomials of trees, Senior Honors Thesis, Darmouth College (2003)

[11] Gessel, Ira M. Multipartite P-partitions and inner products of skew Schur functions, Combinatorics and algebra (Boulder, Colo., 1983) (Contemp. Math.), Volume 34, Amer. Math. Soc., Providence, RI, 1984, pp. 289-301 | DOI | MR | Zbl

[12] Hasebe, Takahiro; Tsujie, Shuhei Order quasisymmetric functions distinguish rooted trees, J. Algebraic Combin., Volume 46 (2017) no. 3-4, pp. 499-515 | DOI | MR | Zbl

[13] Hazewinkel, Michiel The algebra of quasi-symmetric functions is free over the integers, Adv. Math., Volume 164 (2001) no. 2, pp. 283-300 | DOI | MR | Zbl

[14] Heil, S.; Ji, C. On an algorithm for comparing the chromatic symmetric functions of trees, Australas. J. Combin., Volume 75 (2019), pp. 210-222 | MR | Zbl

[15] Huryn, Jake; Chmutov, Sergei A few more trees the chromatic symmetric function can distinguish, Involve, Volume 13 (2020) no. 1, pp. 109-116 | DOI | MR | Zbl

[16] Lam, Thomas; Pylyavskyy, Pavlo P-partition products and fundamental quasi-symmetric function positivity, Adv. in Appl. Math., Volume 40 (2008) no. 3, pp. 271-294 | MR | Zbl

[17] Liu, Ricky Ini; Weselcouch, Michael P-partition generating function equivalence of naturally labeled posets, J. Combin. Theory Ser. A, Volume 170 (2020), p. 105136, 31 | DOI | MR | Zbl

[18] Liu, Ricky Ini; Weselcouch, Michael P-partitions and quasisymmetric power sums, Int. Math. Res. Not. IMRN (2021) no. 18, pp. 13975-14015 | DOI | MR

[19] Loebl, Martin; Sereni, Jean-Sébastien Isomorphism of weighted trees and Stanley’s isomorphism conjecture for caterpillars, Ann. Inst. Henri Poincaré D, Volume 6 (2019) no. 3, pp. 357-384 | DOI | MR | Zbl

[20] Loehr, Nicholas A.; Warrington, Gregory S. A rooted variant of Stanley’s chromatic symmetric function (2022+) | arXiv

[21] Malvenuto, Claudia; Reutenauer, Christophe Duality between quasi-symmetric functions and the Solomon descent algebra, J. Algebra, Volume 177 (1995) no. 3, pp. 967-982 | DOI | MR | Zbl

[22] Martin, Jeremy L.; Morin, Matthew; Wagner, Jennifer D. On distinguishing trees by their chromatic symmetric functions, J. Combin. Theory Ser. A, Volume 115 (2008) no. 2, pp. 237-253 | DOI | MR | Zbl

[23] McNamara, Peter R. W.; Ward, Ryan E. Equality of P-partition generating functions, Ann. Comb., Volume 18 (2014) no. 3, pp. 489-514 | DOI | MR | Zbl

[24] Orellana, Rosa; Scott, Geoffrey Graphs with equal chromatic symmetric functions, Discrete Math., Volume 320 (2014), pp. 1-14 | DOI | MR | Zbl

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

[26] Smith, Isaac; Smith, Zane; Tian, Peter Symmetric Chromatic Polynomial of Trees (2015) | arXiv

[27] Stanley, Richard P. Ordered structures and partitions, Ph. D. Thesis, Harvard University (1971)

[28] Stanley, Richard P. Ordered structures and partitions, American Mathematical Society, Providence, R.I., 1972, iii+104 pages (Memoirs of the American Mathematical Society, No. 119) | MR

[29] 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

[30] Stanley, Richard P. Enumerative combinatorics. Vol. 2, Cambridge Studies in Advanced Mathematics, 62, Cambridge University Press, Cambridge, 1999, xii+581 pages | DOI | MR

[31] 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

[32] The Sage Developers SageMath, the Sage Mathematics Software System (Version 8.9) (2019)

[33] Zhou, Jeremy Reconstructing rooted trees from their strict order quasisymmetric functions (2022+) | arXiv

Cited by Sources: